2011-0010

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

dp
在当前行扩展所有可能已经设置的炸弹数0..b,
对每个情况有四种状态需要计算，
1.一个都不炸
2.炸第一个
3.炸第二个
4.炸第三个
5.炸第一个和第三个

其他的情况就算炸了也不会被取到，就直接忽略了。关于题目的负数，因为没有规定炸弹一定要用完，于是负数的那个格子也肯定不会被炸到。不喜欢有负数就可以直接置0了。
关于情况有很多不必要的计算。。比如前一次炸了1，或者1，3，那么这次肯定不会炸1。具体参见我的程序

下面是我的程序

{{{
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
int dp[1001][5];
int main()
{
    int n,b,a1,a2,a3;
    while (scanf("%d%d",&n,&b) != EOF){
        memset(dp,0,sizeof dp);
        for (int i = 1; i <= n; ++i){
            scanf("%d%d%d",&a1,&a2,&a3);
            for (int j = b; j > 1; --j){
                dp[j][0] = max(dp[j-1][0],
                            max(dp[j][0],
                                max(dp[j][1],
                                    max(dp[j][2],
                                        max(dp[j][3],dp[j][4])))));
                dp[j][1] = max(dp[j-1][0],max(dp[j-1][2],dp[j-1][3])) + a1;
                dp[j][2] = max(dp[j-1][0],
                                max(dp[j-1][1],
                                    max(dp[j-1][3],dp[j-1][4]))) + a2;
                dp[j][3] = max(dp[j-1][0],
                                max(dp[j-1][1],dp[j-1][2])) + a3;
                dp[j][4] = max(max(dp[j-2][0],dp[j-2][2]) + a1 + a3,
                            max(dp[j-2][1] + a3,dp[j-2][3]+a1));
            }
            dp[1][0] = max(max(dp[1][1],dp[1][0]),max(dp[1][2],dp[1][3]));
            dp[1][1] = a1;
            dp[1][2] = a2;
            dp[1][3] = a3; 
        }
          int ans = 0;
          ans = max(max(max(dp[b][0],dp[b][1]),max(dp[b][2],dp[b][3])),dp[b][4]);
        printf("%d\n",ans);
    }
}
}}}


by 武慕邪

dp

在当前行扩展所有可能已经设置的炸弹数0..b,

对每个情况有四种状态需要计算，

1.一个都不炸

2.炸第一个

3.炸第二个

4.炸第三个

5.炸第一个和第三个

其他的情况就算炸了也不会被取到，就直接忽略了。关于题目的负数，因为没有规定炸弹一定要用完，于是负数的那个格子也肯定不会被炸到。不喜欢有负数就可以直接置0了。

关于情况有很多不必要的计算。。比如前一次炸了1，或者1，3，那么这次肯定不会炸1。具体参见我的程序

下面是我的程序

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int dp[1001][5];
int main()
{
    int n,b,a1,a2,a3;
    while (scanf("%d%d",&n,&b) != EOF){
        memset(dp,0,sizeof dp);
        for (int i = 1; i <= n; ++i){
            scanf("%d%d%d",&a1,&a2,&a3);
            for (int j = b; j > 1; --j){
                dp[j][0] = max(dp[j-1][0],
                            max(dp[j][0],
                                max(dp[j][1],
                                    max(dp[j][2],
                                        max(dp[j][3],dp[j][4])))));
                dp[j][1] = max(dp[j-1][0],max(dp[j-1][2],dp[j-1][3])) + a1;
                dp[j][2] = max(dp[j-1][0],
                                max(dp[j-1][1],
                                    max(dp[j-1][3],dp[j-1][4]))) + a2;
                dp[j][3] = max(dp[j-1][0],
                                max(dp[j-1][1],dp[j-1][2])) + a3;
                dp[j][4] = max(max(dp[j-2][0],dp[j-2][2]) + a1 + a3,
                            max(dp[j-2][1] + a3,dp[j-2][3]+a1));
            }
            dp[1][0] = max(max(dp[1][1],dp[1][0]),max(dp[1][2],dp[1][3]));
            dp[1][1] = a1;
            dp[1][2] = a2;
            dp[1][3] = a3; 
        }
          int ans = 0;
          ans = max(max(max(dp[b][0],dp[b][1]),max(dp[b][2],dp[b][3])),dp[b][4]);
        printf("%d\n",ans);
    }
}

by 武慕邪