首页 > 代码库 > [ CodeVS冲杯之路 ] P1169

[ CodeVS冲杯之路 ] P1169

2024-08-14 15:37:03   218人阅读

　　不充钱，你怎么AC？

　　题目：http://codevs.cn/problem/1169/

 

　　感觉这题目好恐怖，莫名其妙乱码一堆就AC了……

　　它看上去是两个子问题，实际上可以看成从起点找两条不相交的路径使得经过的数和最大

　　用 f[i][j][k][l] 表示第一条走到了 (i,j) 第二条走到了 (k,l)

　　技术分享

　　目标状态是 f[n][m-1][n-1][m]

　　一开始我也没仔细去想，就莫名其妙码了一堆交上去了，本以为会WA，结果A了？！

　　后面我仔细证明了一下，它是这样的

　　首先 l 是从 j+1 开始的，这个点非常关键，它控制住列下标，永远会比 j 大，也就是第二条线始终在第一条的右边，这就保证了两线不相交

　　但是它会从 [l-1] 转移过来，也就是从 j=l 的地方转移，不过这没有关系，因为 j=l 的状态永远是 0，因为循环的时候根本不会使 j=l

　　因为终点的分数是 0，所以目标状态就是终点左边和上面的两个点

 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<cmath> 5 #include<iostream> 6 #include<algorithm> 7 using namespace std; 8  9 int f[51][51][51][51],n,a[51][51],m;10 int main()11 {12     scanf("%d%d",&n,&m);13     int i,j,k,l;14     for (i=1;i<=n;i++)15         for (j=1;j<=m;j++) scanf("%d",&a[i][j]);16     for (i=1;i<=n;i++)17         for (j=1;j<=m;j++)18             for (k=1;k<=n;k++)19                 for (l=j+1;l<=m;l++) f[i][j][k][l]=max(max(f[i][j-1][k-1][l],f[i-1][j][k][l-1]),max(f[i][j-1][k][l-1],f[i-1][j][k-1][l]))+a[i][j]+a[k][l];20     printf("%d\n",f[n][m-1][n-1][m]);21     return 0;22 }

 

[ CodeVS冲杯之路 ] P1169


联系
我们