社区讨论

为啥压两位就有问题

P9743「KDOI-06-J」旅行参与者 1已保存回复 0

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@m3115eea
此快照首次捕获于
2024/11/03 11:25
去年
此快照最后确认于
2025/11/04 15:28
4 个月前
查看原帖
代码:
CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int n,m,k,A[50][50],B[50][50],dp[10][10][51][51][95],lans[50][50];
signed main()
{
	cin>>n>>m>>k;
	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++)
		for(int j = 1;j <=m;j++)
			cin>>B[i][j];
	for(int i = 0;i <n;i++)
		for(int j = 0;j <m;j++)
			if(i*A[1][1]+j*B[1][1]<=k)
				dp[1][1][i][j][i*A[1][1]+j*B[1][1]]=1;
	for(int i = 1;i <=n;i++)
		for(int j = 1;j <=m;j++)
		{
			if(i==1&&j==1)continue;
			for(int a = 0;a <51;a++)
				for(int b = 0;b <51;b++)
					for(int p = 0;p <95;p++)
						dp[i%2][j%2][a][b][p]=0;
			for(int a = 0;a <=n-i;a++)
				for(int b = 0;b <=m-j;b++)
					for(int p = 0;p <=k;p++)
					{
						int pp=i,q=j;
						i%=2;j%=2;
dp[i][j][a][b][p]=0;
if(a-1>=0&&p-A[pp][q]>=0)dp[i][j][a][b][p]+=dp[i][j][a-1][b][p-A[pp][q]];
if(b-1>=0&&p-B[pp][q]>=0)dp[i][j][a][b][p]+=dp[i][j][a][b-1][p-B[pp][q]];
if(a>=1&&b>=1&&p-A[pp][q]-B[pp][q]>=0)
	dp[i][j][a][b][p]-=dp[i][j][a-1][b-1][p-A[pp][q]-B[pp][q]];
if(pp!=1)dp[i][j][a][b][p]+=dp[(i+1)%2][j][a+1][b][p];
if(q!=1)dp[i][j][a][b][p]+=dp[i][(j+1)%2][a][b+1][p];
dp[i][j][a][b][p]+=mod;
dp[i][j][a][b][p]%=mod;
						i=pp,j=q;
					}
			lans[i][j]=dp[i%2][j%2][0][0][k];
		}
	for(int i = 1;i <=n;i++)
	{
		for(int j = 1;j <=m;j++)
			cout<<lans[i][j]<<" ";
		cout<<"\n";
	}
	return 0;
}

回复

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

正在加载回复...