4 条题解
-
10
方格取数2 P1231
思路
动态规划
完整代码
#include <bits/stdc++.h> using namespace std; int n; int x,y,z; int d[55][55]; int f[55][55][55][55]; int main() { cin >> n ; while(cin>>x>>y>>z && x) d[x][y] = z; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int l = 1; l <= n; l++) { int k=i+j-l; if(k>=1&&k<=n) f[i][j][l][k] = max(max(f[i - 1][j][l - 1][k], f[i][j - 1][l][k-1]), max(f[i - 1][j][l][k - 1], f[i][j - 1][l - 1][k])) + d[i][j]+d[l][k]; if(j == k) f[i][j][l][k] -= d[l][k]; } } } cout << f[n][n][n][n]; return 0; }我有一个疑问，怎么可以没赞呢？ 谁来教教我呀
-
3
hetao24883491
LV 10
@ 2023-12-16 10:23:02
这道题与《禾木取数》类似，抄下来改一下就好了
#include <iostream> using namespace std; int n,a[30][30]={},f[30][30][30][30]={}; int main(void){ cin>>n; while(1){ int x,y,z; cin>>x>>y>>z; if(x==0&&y==0&&z==0) break; a[x][y]=z; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) for(int l=1;l<=n;l++) f[i][j][k][l]=max(max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]),max(f[i][j-1][k-1][l],f[i][j-1][k][l-1]))+((i==k&&j==l)?a[i][j]:a[i][j]+a[k][l]); cout<<f[n][n][n][n]; return 0; } -
1
思路
这一题和课上第二个OJ题比较类似，唯一需要注意的是这道题，道路可以交叉 $\\$（1）状态定义：$f[i][j][l][k] $表示第1个方格到达$(i,j)$，且表示第2个方格到达$(l,k)$时取到的最大值，显然依旧满足$i+j==l+k$。 $\\$（2）状态转移：此时$i、j、l$都可以从$1$循环到$n$,$k$可由$k=i+j-l$得到，之后当$1<=k<=n$时可以进行状态转移，可能转移的方式和课上练习一样有4种。之后注意这里需要去重复，如果$j==k$时，说明两个道路到达同一个节点，那么该节点值计算了2次，需要减去1次。 $\\$（3）最终结果：$f[n][n][n][n]$代码
#include<bits/stdc++.h> using namespace std; int n,x,y,s; int a[55][55], f[55][55][55][55]; int main() { cin>>n; while(cin>>x>>y>>s && x) a[x][y] = s; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) for(int l = 1; l <= n; l++) { int k=i+j-l; if(k>=1&&k<=n) f[i][j][l][k] = max(max(f[i - 1][j][l - 1][k], f[i][j - 1][l][k-1]), max(f[i - 1][j][l][k - 1], f[i][j - 1][l - 1][k])) + a[i][j]+a[l][k]; if(j == k) f[i][j][l][k] -= a[l][k]; } cout<< f[n][n][n][n]; return 0; } -
-2
hetao435252 LV 4 @ 2023-10-19 13:22:46
动规，因为要两条路径，所以四层循环，数据规模也爆不了；
using namespace std; int a[11][11],b[11][11][11][11],sum; int n; int main(){ cin>>n; int x=1,y=1,num=1; while(!(x==0 && y==0 && num==0)){ cin>>x>>y>>num; a[x][y]=num; } b[1][1][1][1]=a[1][1]; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ for(int k=1;k<=n;k++){ for(int f=1;f<=n;f++){ int maxx=-1; if(i==k&&j==f)continue; if(b[i][j-1][k][f-1]>maxx) maxx=b[i][j-1][k][f-1]; if(b[i-1][j][k-1][f]>maxx) maxx=b[i-1][j][k-1][f]; if(b[i][j-1][k-1][f]>maxx) maxx=b[i][j-1][k-1][f]; if(b[i-1][j][k][f-1]>maxx) maxx=b[i-1][j][k][f-1]; if(maxx==-1)continue; b[i][j][k][f]=maxx+a[i][j]+a[k][f]; cout<<b[n][n-1][n-1][n]+a[n][n]; return 0; }
- 1