题解 | 小红笔试

#include<bits/stdc++.h>
using namespace std;

const int N=2e3+10;

int n,T;
int dp[N][N];

int main(){
//	ios::sync_with_stdio(false);
//	cin.tie(0);
	
	cin>>n>>T;
	vector<pair<int,int>> vpr[N];
	int a,b,c,d;
	for(int i=1;i<=n;i++){
		cin>>a>>b>>c>>d;
		vpr[i].push_back({a,b});
		vpr[i].push_back({c,d});
	}
	
	for(int i=1;i<=n;i++){
		int ta=vpr[i][0].first;
		int sa=vpr[i][0].second;
		int tb=vpr[i][1].first;
		int sb=vpr[i][1].second;
		for(int j=0;j<=T;j++){
			dp[i][j]=dp[i-1][j];
			if(j>=tb){
				dp[i][j]=max(dp[i][j],dp[i-1][j-tb]+sb);
			}
			if(j>=ta){
				dp[i][j]=max(dp[i][j],dp[i-1][j-ta]+sa);
			}
		}
	}
	string res="";
	int time=T;
	for(int i=n;i>=1;i--){
		int ta=vpr[i][0].first;
		int sa=vpr[i][0].second;
		int tb=vpr[i][1].first;
		int sb=vpr[i][1].second;
		if(time>=ta&&dp[i][time]==dp[i-1][time-ta]+sa){
			res='A'+res;
			time-=ta;
		}else if(time>=tb&&dp[i][time]==dp[i-1][time-tb]+sb){
			res='B'+res;
			time-=tb;
		}else{
			res='F'+res;
		}
	}
	cout<<res<<endl;
//	cout<<dp[n][T]<<endl;
    return 0;
}