社区讨论
数据太水了
P1070[NOIP 2009 普及组] 道路游戏参与者 4已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @lo7rc8oc
- 此快照首次捕获于
- 2023/10/27 06:30 2 年前
- 此快照最后确认于
- 2023/10/27 06:30 2 年前
我的代码:
CPP#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,p,maxx=-INF,a[520][520],b[520],f[2][520][520];
int left(int x)
{
if(x==1)
return n;
return x-1;
}
int main()
{
// freopen("game.in","r",stdin);
// freopen("game.out","w",stdout);
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
memset(f,-0x3f,sizeof f);
for(int i=1;i<=n;i++)
f[1][i][1]=a[i][1]-b[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=p;j++)
maxx=max(maxx,f[1][i][j]);
for(int i=2;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
int l=left(j);
f[i&1][j][1]=maxx+a[j][i]-b[j];
for(int k=2;k<=p;k++)
f[i&1][j][k]=f[(i-1)&1][l][k-1]+a[j][i];
}
for(int j=1;j<=n;j++)
for(int k=1;k<=p;k++)
maxx=max(maxx,f[i&1][j][k]);
}
int ans=-INF;
for(int i=1;i<=n;i++)
for(int j=1;j<=p;j++)
ans=max(ans,f[m&1][i][j]);
printf("%d",ans);
}
时间复杂度 ,但AC
回复
共 5 条回复,欢迎继续交流。
正在加载回复...