跳至正文

NOIP 2006 提高组 1 能量项链

  因为以前做过这一题,所以很快就写出来了,不过在一个细节的地方纠结了好久,具体位置见注释。
  思路和以前是一样的,f[i][j] = max(map[i] map[i + a] map[i + j] + f[i][a] + f[i + a][j – i]); f[i][j]表示从第i个珠子往后j个所能获得的最大能量,然后代码就写出来了:

#include <stdio.h>
int n;
int map[200];
unsigned f[100][101];

void deal(int a, int b)
{
        int i;
        unsigned max = 0, t;
        for(i = 1; i < b; i++){
                t = map[a] map[a + i] map[a + b]
                                        //这里的a+b写成了a + i + 1
                        + f[a][i] + f[(a + i) % n][b – i];
                if(t > max){
                        max = t;
                }
        }
        f[a][b] = max;
}

int main(void)
{
        int i, j;
        unsigned max;
//      freopen("abc.txt", "r", stdin);
        scanf("%d", &n);
        for(i = 0; i < n; i++){
                scanf("%d", &map[i]);
                map[i + n] = map[i];
        }
        for(j = 2; j <= n; j++){
                for(i = 0; i < n; i++){
                        deal(i, j);
                }
        }
        max = 0;
        for(i = 0; i < n; i++){
                if(max < f[i][n]){
                        max = f[i][n];
                }
        }
        printf("%d\n", max);
//      getch();
        return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注