50分求助,一看就懂的超短背包
  • 板块P1174 打砖块
  • 楼主Wens
  • 当前回复0
  • 已保存回复0
  • 发布时间2020/12/3 06:31
  • 上次更新2023/11/5 06:50:17
查看原帖
50分求助,一看就懂的超短背包
213196
Wens楼主2020/12/3 06:31
#include<bits/stdc++.h>
#define N 205
using namespace std;

inline int Max(int a,int b){return a>b?a:b;}

int n,m,K,ans;
int v[N][N],w[N][N],f[N][N];

int main(){
	cin>>n>>m>>K;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			string ch;
			cin>>v[i][j]>>ch;
			if(ch[0]=='N')w[i][j]=1;
		}
	}
	for(int i=1;i<=m;++i){
		int val=0,cost=0;
		for(int k=K;k>=0;--k)f[i][k]=f[i-1][k]; 
		for(int j=n;j>=1;--j){
			val+=v[j][i];
			cost+=w[j][i];
			for(int k=K;k>=cost;--k){
				f[i][k]=Max(f[i][k],f[i-1][k-cost]+val);
				ans=Max(f[i][k],ans);
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}
2020/12/3 06:31
加载中...