社区讨论

60求助

P1006[NOIP 2008 提高组] 传纸条参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo9dnvo4
此快照首次捕获于
2023/10/28 09:42
2 年前
此快照最后确认于
2023/10/28 09:42
2 年前
查看原帖
CPP
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
const int maxn=55;
using namespace std;

int n,m,a[maxn][maxn],dp[2*maxn][maxn][maxn];
int main() {
	scanf("%d%d",&m,&n);
	for(int i=1; i<=m; i++)
		for(int j=1; j<=n; j++)
			scanf("%d",&a[i][j]);
	for(int k=2; k<=m+n; k++) {
		for(int i=max(1,k-m); i<=min(n,k-1)&&i<k; i++) {
			for(int j=max(1,k-m); j<=min(n,k-1)&&j<k; j++) {

				int t=a[i][k-i];
				if(i!=j)t=t+a[j][k-j];
				for(int aa=0; aa<=1; aa++) {
					for(int b=0; b<=1; b++) {
						dp[k][i][j]=max(dp[k][i][j],dp[k-1][i-aa][j-b]+t);
					}
				}
			}
		}
	}

	printf("%d\n", dp[n + m][n][n]);

	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...