一、解题思路

观察题面，发现是一道板里板气的可行性

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;
}

[ABC271D] Flip and Adjust 题解

文章操作

一、解题思路

二、代码展示

相关推荐

评论

[ABC271D] Flip and Adjust 题解