P1004 解题思路： 1.第一想法是DFS，但是双路两遍DFS不能保证最优解，双路同时DFS是能够想到的。 双路DFS实现也需要剪枝。 2.动态规划，类似01背包，思维数组记录每个状态。 动态规划代码实现：
#include<iostream> #define REP(i,a,b) for(int i=(a);i<=(b);i++) using namespace std; int a[51][51]; int sum[51][51][51][51]; int n,i,j,h,k,x,z,y; int main() { cin>>n>>x>>y>>z; while (x&&y&&z) { a[x][y]=z; cin>>x>>y>>z; } REP(i,1,n) REP (j,1,n) REP (h,1,n) REP (k,1,n) { sum[i][j][h][k]=max(max(sum[i-1][j][h-1][k],sum[i][j-1][h][k-1]),max(sum[i-1][j][h][k-1],sum[i][j-1][h-1][k]))+a[i][j]; if(i!=h&&j!=k) sum[i][j][h][k]+=a[h][k]; } cout<<sum[n][n][n][n]; }动态规划复习： 1.01背包 经典例题 P1910 代码实现：
#include<iostream> using namespace std; long long n,x,a[1020],b[1020],c[1020],f[1020][1020]; long long maxx=-10,m,n1; int main() { cin>>n>>m>>x; for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i]; for(int i=1;i<=n;i++) for(int j=m;j>=b[i];j--) for(int z=x;z>=c[i];z--) f[j][z]=max(f[j][z],f[j-b[i]][z-c[i]]+a[i]); cout<<f[m][x]; }