社区讨论
为啥压两位就有问题
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 条回复,欢迎继续交流。
正在加载回复...