【codeforces 803E】Roma and Poker
2024-08-28 19:27:36
【题目链接】:http://codeforces.com/contest/803/problem/E
【题意】
给你一个不完整的胜负平序列(不完整是指中间有些地方为问号,让你自己选择胜负平)
让你复原一个有关胜、负、平、的结果序列
(从左到右按时间有序)
要求在前n-1秒;
胜负场数之差任意时刻都不能超过k;
且在第n秒,胜负场数值差刚好为k;
【题解】
设f[i][j]表示前i场游戏,胜场与负场的差为j的情况能不能达到;
能达到就为true;并记录是怎么达到的(即是赢一场达到的还是输还是…)
这样进行DP
第一层枚举从0..n-1
然后第二层循环只从-k+1枚举到k-1
这样能保证在进行DP的时候选举的状态都是胜场与负场的差的绝对值小于k的;
然后最后一秒(第n秒是可以为k的)
刚好也能更新到.
【Number Of WA】
0
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 1e3+10;
int n,k;
char f[1100][2*1100];
bool bo[1100][2*1100];
char s[N];
int main()
{
//freopen("F:\\rush.txt","r",stdin);
ios::sync_with_stdio(false),cin.tie(0);//scanf,puts,printf not use
cin >> n >> k;
cin >> (s+1);
bo[0][0+N] = true;
rep1(i,0,n-1)
{
rep1(j,-k+1,k-1)
if (bo[i][j+N])
{
if (s[i+1]=='W' || s[i+1]=='?')
{
bo[i+1][j+N+1] = true;
f[i+1][j+N+1] = 'W';
}
if (s[i+1]=='L' || s[i+1]=='?')
{
bo[i+1][j+N-1] = true;
f[i+1][j+N-1] = 'L';
}
if (s[i+1]=='D' || s[i+1]=='?')
{
bo[i+1][j+N] = true;
f[i+1][j+N] = 'D';
}
}
}
if (bo[n][-k+N]||bo[n][k+N])
{
string ans = "";
int now = bo[n][k+N]?N+k:N-k;
rep2(i,n,1)
{
ans = f[i][now] + ans;
if (f[i][now]=='W')
now--;
if (f[i][now]=='L')
now++;
}
cout << ans << endl;
}
else
cout << "NO" << endl;
return 0;
}
最新文章
- Java三大框架 介绍
- ANNOTATION PROCESSING 101 by Hannes Dorfmann — 10 Jan 2015
- CentOS 7 虚拟机无法开机问题
- ZeroMQ接口函数之 :zmq_null - 无安全和加密
- linux第三方程序移植
- kali 在线教学群 第一次 公开课 小结(1)
- iOS学习笔记---c语言第十一天
- redis专题--slow log详解
- ISO和UDF光盘格式、扩展ISO9660----Joliet和Romeo文件系统
- delphi调用外部程序打开文件
- ABP官方文档翻译 3.1 实体
- 实现CString的Format功能,支持跨平台
- 计蒜客	2019 蓝桥杯省赛 B 组模拟赛(三)数字拆分
- ProtocolError: <;ProtocolError for 127.0.0.1/RPC2: 401 Unauthor.
- bzoj 2301
- linux基础命令---显示进程ps
- 基于docker的wekan部署
- VB.NET中的DLL编写和调用的最简单示例
- JCR分区(WOS或Thomson Reuters或汤姆森 路透)和中科院分区(附网址及查询方法)
- [转]请用fontAwesome代替网页icon小图标
热门文章
- JavaFX本地应用自己主动更新功能的实现FXLauncher
- Codeforces Round #244 (Div. 2)D (后缀自己主动机)
- [think in java]第12章 通过异常处理错误
- ASIHTTPRequest框架的简单使用
- php简单表格函数
- 软件开发 —— 极限编程(XP:Extreme Programming)
- Hyper和Vmware冲突,Device/Credential Guard 不兼容
- ES6和Node容易搞混淆的点
- iOS数组越界
- vue插件 vue-seamless-scroll 无缝滚动插件ES6使用总结