跳至正文

Noip 2010 提高组 第二题 乌龟棋

  • OI路程

  在考场上我的思想是这么的,f[n +
j] = max{当在n这个位置时还有布数为j的卡片|f[n] + map[n + j]},后来发现这么是不行的,因为f[n + j]不是最大但也可能有更好的取值,因为它可以留下另外一张卡片,只有10分呢!
  后来,我又想了另外一种算法,用一个维护一个栈,然后判断所有的可能性(说白了就是暴力枚举。),很自然读者都想到了两字——Time Out(超时),不过也有30分!
  经过我的冥思苦想,终于是想到了另外一个方程,题目说的很清楚,每种卡片最多40张,那么就用卡片来枚举,f[a][b][c][d] = max{f[a –
1][b][c][d], f[a][b – 1][c][d], f[a][b][c – 1][d], f[a][b][c][d – 1]} + map[1
a + 2
b + 3 c + 4 d];
  很自然的,这个方程式无敌的~AC了,只可惜是在家里而不是考场。。

#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
#define index_map
int map[351];
int f[41][41][41][41];
int card[4];
int used[4];

void srch(int n)
{
        int i;
        if(n == 4){
                int t = 0;
                if(used[0] != 0){
                        t = max(t, f[used[0] – 1][used[1]][used[2]][used[3]]);
                }
                if(used[1] != 0){
                        t = max(t, f[used[0]][used[1] – 1][used[2]][used[3]]);
                }
                if(used[2] != 0){
                        t = max(t, f[used[0]][used[1]][used[2] – 1][used[3]]);
                }
                if(used[3] != 0){
                        t = max(t, f[used[0]][used[1]][used[2]][used[3] – 1]);
                }
                f[used[0]][used[1]][used[2]][used[3]] = t + map[used[0] + used[1]  2 +  used[2]  3 + used[3] * 4 + 1];
                return;
        }
        for(i = 0; i <= card[n]; i++){
                used[n] = i;
                srch(n + 1);
        }
}

int main(void)
{
        int i, j, k, t;
        int n, m;
//      freopen("tmp.in", "r", stdin);
        scanf("%d%d", &n, &m);
        for(i = 1; i <= n; i++){
                scanf("%d", &map[i]);
        }
        for(i = 1; i <= m; i++){
                scanf("%d", &t);
                card[t – 1]++;
        }
        srch(0);
        printf("%d\n", f[card[0]][card[1]][card[2]][card[3]]);
//      getch();
        return 0;
}

发表评论

您的电子邮箱地址不会被公开。