为神马TLE了啊
  • 板块学术版
  • 楼主csd2011
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/8/3 17:02
  • 上次更新2023/11/3 06:07:48
查看原帖
为神马TLE了啊
551510
csd2011楼主2023/8/3 17:02
#include<bits/stdc++.h>
using namespace std;
int dp[2009][2009],f[2009][2009],n,m,a[2009][2009];
const int mod=1e9+7;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++)f[i][1]=1,dp[i][1]=dp[i-1][1]+a[i][1];
	for(int i=1;i<=m;i++)f[1][i]=1,dp[1][i]=dp[1][i-1]+a[1][i];
	for(int i=2;i<=n;i++)
	{
		for(int j=2;j<=m;j++)
		{
			dp[i][j]=a[i][j]+max(dp[i-1][j],dp[i][j-1]);
			if(dp[i-1][j]==dp[i][j-1])f[i][j]=(f[i-1][j]+f[i][j-1])%mod;
			else if(dp[i-1][j]>dp[i][j-1])f[i][j]=f[i-1][j]%mod;
			else f[i][j]=f[i][j-1]%mod;
			f[i][j]%=mod;
		}
	}
	cout<<dp[n][m]<<endl<<f[n][m];
}

西洋棋盘可以看成一个 N*M 的网格。西洋棋可以摆放在任何一个格子里,

而不是网格线的交叉点上。

维多利加将一个棋子放在了左上角的格子上。她试着移动这个棋子,棋子只

会向右或者向下移动。

每个格子有一个权值,维多利加想知道,从左上角到右下角的所有路径中:

1.经过的格子的权值和最大是多少?

2.权值和最大的路径一共有多少条? Input 第一行两个整数 N,M。

接下来 N 行,每行 M 个整数,表示每个格子的权值。

Output 输出两行,第一行表示最大权值和,第二行表示权值和最大的路径数除以

1e9+7 的余数。

2023/8/3 17:02
加载中...