RT
Code:
#include<bits/stdc++.h> using namespace std; inline int read(){ int res=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar(); return res*f; } inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x<10) putchar(x+'0'); else write(x/10),putchar(x%10+'0'); } int T,N,M,g[110][110],dp[110],SP[10010],F[10010],ans; inline int dfs(int D1,int D2,int C){ memset(SP,0,sizeof(SP)); memset(F,0,sizeof(F)); for(int i=1;i<=N;i++){ for(int j=g[D1][i];j<=C;j++){ if(F[j-g[D1][i]]+g[D2][i]+C-(SP[j-g[D1][i]]+g[D1][i])>F[j]+C-SP[j]){ F[j]=F[j-g[D1][i]]+g[D2][i]; SP[j]=SP[j-g[D1][i]]+g[D1][i]; } } } return F[C]+C-SP[C]; } int main(){ T=read();N=read();M=read(); for(int i=1;i<=T;i++){ for(int j=1;j<=N;j++){ g[i][j]=read(); } } for(int i=1;i<=T;i++) dp[i]=M; for(int i=1;i<=T;i++){ for(int j=i+1;j<=T;j++){ dp[j]=max(dp[j],dfs(i,j,dp[i])); ans=max(ans,dp[j]); } } write(ans);putchar('\n'); return 0; }
全部评论
(1) 回帖