ZCMU - 1601: 卡斯丁狗去挖矿

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof a);
using namespace std;
typedef long long ll;
// 01背包 - 三维数组，前面两个相当于二维数组的[i]，最后一个相当于二维数组的[j]
int dp[310][310][310];
int main()
{
    int m,n,x;
    while(~scanf("%d%d",&m,&n))
    {
        mem(dp,0);
        int rs=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=i;j++)
            {
                scanf("%d",&x);
//                for(int k=x;k<=m;k++) // 也可以AC
//                {
//                    dp[i][j][k]=max(max(dp[i-1][j-1][k],dp[i-1][j][k]),max(dp[i-1][j][k-x]+x,dp[i-1][j-1][k-x]+x));
//                }
                for(int k=0;k<=m;k++) // 对每个坐标进行 01背包
                {
                    if(k>=x)
                        dp[i][j][k]=max(max(dp[i-1][j-1][k],dp[i-1][j][k]),max(dp[i-1][j][k-x]+x,dp[i-1][j-1][k-x]+x));
                    else
                        dp[i][j][k]=max(dp[i-1][j-1][k],dp[i-1][j][k]);
                }
                rs=max(rs,dp[i][j][m]); // 因为会集中在每个坐标（01背包）的末尾，所以对末尾取max即可
            }
        printf("%d\n",rs); // dp[n][n][m] 这种是错误的思路，因为这只是代表最后一次的01背包的max，而每次坐标撸第三个for_k的时候，它们每个坐标之间都是互相独立的
    }
    return 0;
}