$k代表两条路径同时走了k步的阶段,在图中也代表着横纵坐标之和,由于$$i_1+j_1=i_2+j_2$$,所以可以把 f[$$i_1$$][$$j_1$$][$$i_2$$][$$j_2$$]转化为f[$$k$$][$$i_1$$][$$i_2$$]来降维$
#include<bits/stdc++.h>
using namespace std;
const int N=12;
int f[N*2][N][N];
int w[N][N];
int n;
int main(){
cin>>n;
int a,b,c;
while(cin>>a>>b>>c) w[a][b]=c;
for(int i=2;i<=n*2;i++){
for(int i1=1;i1<=n;i1++){
for(int i2=1;i2<=n;i2++){
int j1=i-i1,j2=i-i2;
if(j1>=1&&j1<=n&&j2>=1&&j2<=n){
int t=w[i1][j1];
if(i1!=i2) t+=w[i2][j2];
for(int a=0;a<=1;a++){ //两种写法均可
for(int b=0;b<=1;b++){
f[i][i1][i2]=max(f[i][i1][i2],f[i-1][i1-a][i2-b]+t);
}
}
// int &x=f[i][i1][i2];
// x=max(x,f[i-1][i1-1][i2-1]+t);
// x=max(x,f[i-1][i1-1][i2]+t);
// x=max(x,f[i-1][i1][i2-1]+t);
// x=max(x,f[i-1][i1][i2]+t);
}
}
}
}
cout<<f[2*n][n][n]<<endl;
}
大佬我想问下dp两次会有什么问题QwQ
这个题目dp两次也是可以的,是另一种解法,现在才看到,十分抱歉。
dp两次应该不可以,因为可能第一次dp会取一个最优解导致第二次dp的时候某两个数无法同时取到,但若是两次同时dp就会取到所有的数
dp两次应该不可以,因为可能第一次dp会取一个最优解导致第二次dp的时候某两个数无法同时取到,但若是两次同时dp就会取到所有的数
解释的很好
谢谢,就是没使用markdown语法,看起来不漂亮,哈哈