【背包求具体方案】ABC271 D - Flip and Adjust

哈哈，是谁H和T写反了一直WA

D - Flip and Adjust (atcoder.jp)

题意:

 思路：

直接背包即可

注意具体方案的输出是怎么写的

一般就是从终点开始，往前for循环，动态维护指针j

Code：

#include <bits/stdc++.h>
using namespace std;
//#define int long long 
const int mxn=1e2+10;
const int mxe=5e4+10;
const int mod=1e9+7;
int n,s;
int a[mxn],b[mxn],dp[mxn][10010];//前i个位置能凑出j的方案数
void solve(){
    cin>>n>>s;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=10000;j++){
            if(j>=a[i]){
                dp[i][j]+=dp[i-1][j-a[i]];
            }
            if(j>=b[i]){
                dp[i][j]+=dp[i-1][j-b[i]];
            }
        }
    }
    vector<char> v;
    if(dp[n][s]){
        cout<<"Yes"<<'\n';
        for(int i=n;i>=1;i--){
            if(s>=a[i]&&dp[i-1][s-a[i]]){
                s-=a[i];
                v.push_back('H');
            }else if(s>=b[i]&&dp[i-1][s-b[i]]){
                s-=b[i];
                v.push_back('T');
            }
        }
        reverse(v.begin(),v.end());
        for(int i=0;i<v.size();i++) cout<<v[i];
    }else{
        cout<<"No"<<'\n';
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int __=1;//cin>>__;
    while(__--)solve();return 0;
}