/*10分钟的暴力 意料之中的5分..*/ #include<iostream> #include<cstdio> #include<cstring> #define maxn 1010 using namespace std; int n,m,p,g[maxn][maxn],w[maxn],ans; void Dfs(int now,int v) { if(now>m){ans=max(ans,v);return;} for(int i=1;i<=n;i++) for(int j=1;j<=p;j++) { int vi=0; for(int k=i,r=1;r<=j;r++,k++) vi+=g[k%(n+1)][r+now]; Dfs(now+j,v+vi-w[i]); } } int main() { scanf("%d%d%d",&n,&m,&p); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&g[i][j]); for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=1;i<=n;i++) for(int j=1;j<=p;j++) { int vi=0; for(int k=i,r=1;r<=j;r++,k++) vi+=g[k%(n+1)][r]; Dfs(j,vi-w[i]); } printf("%d ",ans); return 0; }
/* 考场上写的未优化的dp O（n^4） 40分 f[i][j]表示第i分钟 在j位置的最大收益 转移的话 枚举上一次选机器人走了几步 同时可以算出上次的起点 也就有了上个状态到现在的收益 这是考场上写的dp 后来发现有点小问题就是算上次的起点比较麻烦 后来直接不存起点这个状态 f[i]表示第i分钟的最大收益 同样的我们枚举上一次规定机器人走了几步 与此同时我们枚举j 表示上次的起点是谁 这样是j+枚举的步数 巧妙的避开了比较复杂的处理 然后计算收益 实现转移 */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 1010 using namespace std; int n,m,p,g[maxn][maxn],w[maxn],f[maxn]; int main() { //freopen("roadgame.in","r",stdin); //freopen("roadgame.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",&g[i][j]); for(int i=1;i<=n;i++) scanf("%d",&w[i]); memset(f,128,sizeof(f));f[0]=0; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) for(int k=1;k<=p;k++) { if(i-k<0)continue;int vi=0; for(int l=i-k+1,r=j;l<=i;l++,r++)vi+=g[r][l],r%=n; f[i]=max(f[i],f[i-k]-w[j]+vi); } printf("%d ",f[m]); return 0; }
/* 后来看别人博客上的优化 恍然大悟！ 上面的tle的dp很明显慢在计算收益上 然而收益与时间有关系 又不能用差分预处理（后来想想好像也可以 但比较麻烦） 我们枚举k 表示上次选的走几步时 每次的一次相加的 这里可以优化掉他 直接维护总的 因为枚举k的顺序决定了这里j枚举这次得起点会比较简单 这样随着枚举k可以依次算出vi */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 1010 using namespace std; int n,m,p,g[maxn][maxn],w[maxn],f[maxn]; int main() { //freopen("roadgame.in","r",stdin); //freopen("roadgame.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",&g[i][j]); for(int i=1;i<=n;i++) scanf("%d",&w[i]); memset(f,128,sizeof(f));f[0]=0; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++)//这次的出发点 { int r=j-1,vi=0;//vi 表示累计的收益 if(r==0)r=n;vi+=g[r][i]; for(int k=1;k<=p;k++) { if(i-k<0)continue; f[i]=max(f[i],f[i-k]-w[r]+vi); if(r==1)r=n;else r--; vi+=g[r][i-k];//只需要O（1）计算 } } printf("%d ",f[m]); return 0; }