竞赛讨论区 > 90pts 前两个点Wa求解
头像
OdtreePrincess
发布于 2019-11-16 21:16
+ 关注

90pts 前两个点Wa求解

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) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐