今晚ABC D求调
  • 板块学术版
  • 楼主Fat_Fish
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/10/1 22:09
  • 上次更新2023/10/27 09:17:33
查看原帖
今晚ABC D求调
238885
Fat_Fish楼主2022/10/1 22:09
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 100;
int n, s, p[N][N / 10], a[N], b[N], f[N][N / 10], from[N][N / 10];
//unordered_map<int, int> mp;
signed main(){
	ios :: sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> s;
	for(int i = 1; i <= n; ++i){
		cin >> a[i] >> b[i];
		p[i][a[i]] = 'H';
		p[i][b[i]] = 'T';
	}
		
	f[0][0] = 1;
	for(int i = 1; i <= n; ++i){
		for(int j = s; j >= a[i]; --j)
			if(f[i - 1][j - a[i]]){
				from[i][j] = j - a[i];
				f[i][j] = 1;
			}
		for(int j = s; j >= b[i]; --j)
			if(f[i - 1][j - b[i]]){
				from[i][j] = j - b[i];
				f[i][j] = 1;
			}
		for(int j = 0; j <= s; ++j)
			if(f[i][j]) cout << j << ' ';
		cout << '\n';
	}
	if(f[n][s]){
		cout << "Yes\n";
		string ans = "";
		int cur = s;
		for(int i = n; i; --i){
			ans += char(p[i][cur - from[i][cur]]);
			cur = from[i][cur];
		}
		cout << string(ans.rbegin(), ans.rend()) << '\n';
	}else cout << "No\n";
	return 0;
} 
2022/10/1 22:09
加载中...