T3-3:小明的扑克牌
2024-10-02 15:23:46
发布于:天津
第三题
题目大意
给出对数字,我们称第对为。
现在你可以进行次的选择,每次可以选择与其中一个,选A获得一个字符H
,选B获得一个字符T
代表方案,若获得他们的数字累加起来,最后的结果刚好等于,那么输出Yes
与你的选择方案,否则输出No
。
求解是否有这样的选择方案?
思路解析
第一眼看过去,20%的数据范围。非常方便,假如我们将每一次选择的方案搭配全部枚举出来,那么也就是求种选择的全排列,那么递归就可以实现。
- 递归求解全排列
- 判断是否符合sum决定输出内容
bool flag = false; // 代表是否找到方案
void dfs(int count ,string s , int number)
{
if(flag)return ;
if(count == n + 1){
if(number == sum){
flag = true ;
// 可以找到方案
cout << "Yes" << endl;
cout << s << endl;
}
return ; // 选择了n个数字 结束了
}
dfs(count + 1,s + 'H' , number + a[count]); // 选择正面
dfs(count + 1 , s + 'T' , number + b[count]); // 选择反面
}
if(!flag)cout << "No" << endl;
时间复杂度大约为
观察100%的数据,n的最大取值为100,那么递归枚举全排列的方式就不再合适。但是我们也可以观察到,分数sum最大为10000,那么我们可以尝试着使用 动态规划 来求解。
动态规划的时间复杂度为,符合题目要求,紧接着来设计状态。
我们的目的是为了判断是否存在方案可以满足sum的条件,那么使用动态规划来求解的时候,我们可以从起点开始衍生枚举出每一个状态方案的数值,并且每个顶点只遍历一次,符合题目要求,故选择动态规划。
-
设置状态: 我们设置dp[i][j],代表在选取了i个卡牌的时候,数值为j的状态。 那么最后的答案则为dp[n][sum]。假若dp[n][sum]存在,那么则有答案。 因此我们需要给dp[i][j]上变量flag与string,保存当前字符是否存在且方案的排列。
-
状态转移方程 :
对于dp[i][j]来说,他有两种方法可以到达。- 选择正面: 从dp[i-1][j-a[i]] 加一张正面卡牌到达dp[i][j]。
- 选择反面: 从dp[i-1][j-b[i]]加一张反面卡牌到达dp[i][j]
假若存在方法可以到达,则flag为true,string累加对应方案的字符
#include<iostream>
using namespace std;
struct Node{
bool flag ;
string s;
};
Node dp[103][10003];
int a[100003];
int b[100003];
void solve()
{
int n,sum;
cin >> n >> sum;
for(int i = 0 ; i <= n ; i ++ )
{
for(int j = 0 ; j <= sum ; j ++ ){
dp[i][j].flag = false;
dp[i][j].s = ""; // 清空dp数组
}
}
for(int i = 1 ; i <= n ; i ++ )
{
cin >> a[i] >> b[i];
}
dp[0][0].flag = true;
for(int i = 1 ; i <= n ; i ++ )
{
// 枚举当前选择的数字
for(int j = a[i] ; j <= sum ; j ++ )
{
// 枚举数字从a[i]~sum的情况
if(dp[i-1][j-a[i]].flag){
dp[i][j] .flag = true;
dp[i][j].s = dp[i-1][j-a[i]].s + 'H';
}
}
for(int j = b[i] ; j <= sum ; j ++ )
{
// 枚举数字从b[i]~sum的情况
if(dp[i-1][j-b[i]].flag){
dp[i][j] .flag = true;
dp[i][j].s = dp[i-1][j-b[i]].s + 'T';
}
}
}
if(dp[n][sum].flag)
{
cout << "Yes" << endl << dp[n][sum].s << endl;
}else cout << "No" << endl;
}
int main()
{
int t;
cin >> t;
while(t--)
{
solve();
}
return 0;
}
这里空空如也
有帮助,赞一个