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

悠悠 2024-03-24 14:41 47阅读 0赞

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

![2e41235e14b944c29a8e0ef5836e0fbf.png][]

[D - Flip and Adjust (atcoder.jp)][D - Flip and Adjust _atcoder.jp]

题意:

![f250996a895f48528e7e0c90e2381e9d.png][] 思路：

直接背包即可

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

一般就是**从终点开始，往前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;
    }

[2e41235e14b944c29a8e0ef5836e0fbf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/5e7a88051af44b7b852b9c3780742421.png
[D - Flip and Adjust _atcoder.jp]: https://atcoder.jp/contests/abc271/tasks/abc271_d
[f250996a895f48528e7e0c90e2381e9d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/b21e8ccfc5624a4fa3f695c9209ab568.png