发表于 | 分类于 | 阅读次数:

题目分析：依次选择任意2，3……N-1，N行相加得到一维数mSum；

再对每次产生的一维数组mSum求最大连续子序列的和；

即把二维数组的问题转化为一维数组上的动态规划。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define max(a,b) (a)>(b)?(a):(b)
int main()
{
    //freopen("Sample Input.txt","r",stdin);
    int N;
    int Matrix[100][100];
    int mSum[100];
    int i,j,k,p;
    int MaxSum,Max,sum;
    while ( scanf("%d",&N)!=EOF )
    {
        for ( i = 0; i < N; i++)
            for ( j = 0; j < N; j++)
                scanf("%d",&Matrix[i][j]);
        Max = 0;
        for ( k = 1; k < N; k++)
        {
            for ( i = 0; i + k < N;i++)
            {
                memset(mSum,0,sizeof(mSum));
                for ( j = 0; j <= k; j++)
                {
                    for ( p = 0; p < N;p++)
                        mSum[p] += Matrix[i+j][p];
                }
                MaxSum = 0,sum = 0;
                for ( p = 0; p < N; p++)
                {
                    sum += mSum[p];
                    sum = max(sum,mSum[p]);
                    MaxSum = max(MaxSum,sum);
                }
                if (MaxSum > Max)
                    Max = MaxSum;
            }
        }
        printf("%d\n",Max);
    }
    return 0;
}

发表于 | 分类于 | 阅读次数: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Max(x,y) (x)>(y)?(x):(y)
int map[100][100],N,k;
int max[100][100];
int iPlus[4] = {-1,0,0,1};
int jPlus[4] = {0,-1,1,0};
typedef struct Node{
int x,y;
}Node;
int dfs(int x,int y)
{
    int i,j,temp,m;
    int next_x,next_y;
    if ( max[x][y] != -1)
        return max[x][y];
    m = 0;
    for ( i = 0; i < 4; i++)
    {
        for ( j = 1; j <=k ; j++)
        {
            next_x = x + iPlus[i]*j;
            next_y = y + jPlus[i]*j;
            if ( next_x>=0 && next_x < N && next_y>=0 && next_y < N && map[next_x][next_y] > map[x][y])
            {
                temp = dfs(next_x,next_y);
                m = Max(temp,m);
            }
        }
    }
    max[x][y] = m + map[x][y];
    return max[x][y];
}
int main()
{
    int i,j;
    int m;
    while ( scanf("%d%d",&N,&k), N!=-1 && k!=-1)
    {
        for ( i = 0; i < N; i++)
            for ( j = 0; j < N; j++)
                scanf("%d",&map[i][j]);
        memset(max,-1,sizeof(max));
        m = dfs(0,0);
        printf("%d\n",m);
    }
    return 0;
}

发表于 | 分类于 | 阅读次数:

考虑N种不同立方体最多可以有3×N种立方体选择，再对立方体进行排序排序后解决状态方程
cube[i].max = MAX(cube[i].max,cube[j].max +cube[i].z)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX(x,y) (x)>(y)?(x):(y)
void swap(int *a,int *b)
{
    int t;
    t = *a;
    *a = *b;
    *b = t;
    return;
}
typedef struct DataType
{
    int x;
    int y;
    int z;
    int max;
}DataType;
DataType cube[100];
int cmp(const void *a,const void *b)
{
    DataType *c = (DataType*)a;
    DataType *d = (DataType*)b;
        if(c->x != d->x)
            return d->x - c->x;
        else if ( c->y != d->y )
            return d->y - c->y;
        else
            return d->z - c->z;
}
int main()
{
    //freopen("SampleInput.txt","r",stdin);
    int n,T;
    int i,j,k;
    int xi,yi,zi;
    int maxH;
    T = 1;
    while ( scanf("%d",&n),n)
    {
        k = 0;
        for ( i = 0; i < n; i++)
        {
            scanf("%d%d%d",&xi,&yi,&zi);
            cube[k].x = xi;
            cube[k].y = yi;
            if ( cube[k].x > cube[k].y)
                swap(&cube[k].x,&cube[k].y);
            cube[k++].z = cube[k].z = zi;
            cube[k].x = yi;
            cube[k].y = zi;
            if ( cube[k].x > cube[k].y)
                swap(&cube[k].x,&cube[k].y);
            cube[k++].z = cube[k].z = xi;
            cube[k].x = xi;
            cube[k].y = zi;
            if ( cube[k].x > cube[k].y)
                swap(&cube[k].x,&cube[k].y);
            cube[k++].z = yi;
        }
        qsort(cube,k,sizeof(cube[0]),cmp);  //按照从大到小排序
        maxH = 0;
        for ( i = 0 ; i < k ; i++)
        {
            cube[i].max = cube[i].z;
            for ( j = i - 1; j >= 0; j--)
            {
                if ( cube[i].x < cube[j].x && cube[i].y < cube[j].y )
                    cube[i].max = MAX(cube[i].max,cube[j].max + cube[i].z);
            }
            maxH = MAX(maxH,cube[i].max);
        }
        printf("Case %d: maximum height =%dn",T++, maxH);
    }
    return 0;
}

发表于 | 分类于 | 阅读次数:

貌似是不是北大的《程序设计导引》里面有这题？

简单题，但关键还是要看清题意，Dodo可以在单位时间内从路边直接跳到靠近路边的一颗植株上面，也可以理解成路边到路边的移动是不考虑时间的。令路边的行标为0。还有只要把有花生的(数量大于0）的数据保存下来，

然后qsort一下从头开始找。记住采摘花生也是需要一个单位时间的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
typedef struct Node
{
    int m,n;
    int num;
}Node;
Node peanuts[3000];
int cmp(const void *a,const void *b)
{
    return ((Node*)b)->num - ((Node*)a)->num;
}
int main()
{
    freopen("Sample Input.txt","r",stdin);
    int T,M,N,K,x;
    int i,j,k;
    int time;
    Node dodo;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d%d",&M,&N,&K);
        k = 0;
        for ( i = 1; i <= M; i++)
        {
            for ( j = 1; j <= N; j++)
            {
                scanf("%d",&x);
                if ( x )
                {
                    peanuts[k].m = i;
                    peanuts[k].n = j;
                    peanuts[k].num = x;
                    k++;
                }
            }
        }
        qsort(peanuts,k,sizeof(peanuts[0]),cmp);
        dodo.m = 0;dodo.n = 1;dodo.num = 0;
        for ( i = 0; i < k;i++)
        {
            if ( !dodo.m )
                time = abs(peanuts[i].m - dodo.m) + peanuts[i].m + 1;
            else
                time = abs(peanuts[i].m - dodo.m) + abs(peanuts[i].n - dodo.n) + peanuts[i].m + 1;
            if ( time <= K )
            {
                if ( !dodo.m )
                    K -= (peanuts[i].m - dodo.m + 1);
                else
                    K -= (abs(peanuts[i].m - dodo.m) + abs(peanuts[i].n - dodo.n) +1 );
                dodo.m = peanuts[i].m;
                dodo.n = peanuts[i].n;
                dodo.num += peanuts[i].num;
            }
            else
                break;
        }
        printf("%d\n",dodo.num);
    }
    return 0;
}