[ABC271D] Flip and Adjust 题解

· · 题解

csdn:这里

一、解题思路

观察题面，发现是一道板里板气的可行性dp 所以用一个二维数组dp_{i,j}来表示前i张牌能否组成j 考虑状态转移方程，分析发现，对于一个dp_{i,j}而言，其可行性取决于之前的值是否为真 由此得出状态转移方程：

dp_{i,j+a[i]}=dp_{i-1,j} dp_{i,j+b[i]}=dp_{i-1,j}

由于之前的值只要有一个为真，当前状态便可成立，所以使用 | 号来进行转移

至此，我们解决了问题的第一部分，现在来看第二部分，输出方案。 观察数据范围1 \leq n\leq100 考虑搜索回退并在回退时记录方案

二、代码展示

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[200005],b[200005],m,dp[205][20005];
string s;
void e(int sum,int st){//搜索回退
    if(st<1||sum<1)return;
    if(dp[st-1][sum-a[st]]&&sum-a[st]>=0){//注意（sum-a[st]>=0）防止多记
        e(sum-a[st],st-1);
        s+='H';//记录方案
    }
    else if(dp[st-1][sum-b[st]]&&sum-b[st]>=0){
        e(sum-b[st],st-1);
        s+='T';
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    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<=m;++j)
            dp[i][j+a[i]]|=dp[i-1][j],//dp状态转移
            dp[i][j+b[i]]|=dp[i-1][j];
    if(dp[n][m])cout<<"Yes\n";
    else cout<<"No\n";
    e(m,n);
    cout<<s;
    return 0;
}