[dp状态设计] 实训附加题——最高段位
目录题目描述
背景
香风智乃除了喜欢玩瓶中船之外，还喜欢打竞技游戏。
有一天她被 \(ELO\) 匹配系统坑惨了，一整天都在输。和心爱抱怨了一番之后，聪明的她想出了下面这个题。
题目
可爱的智乃会给你她某一天的游戏记录，这一天她打了 \(n\) 局游戏，赢了 \(B\) 场，当然具体的输赢记得不是很清楚了，她想知道根据这天的游戏记录，她能够达到的最高段位是什么呢？
智乃知道你可能不明白什么是段位系统，所以善良的她打算给你解释一下
- 正常的段位系统有 \(N\) 个段，称第 \(i\) 个段为段位 \(i\)。
- 每个段位都有 \(m\) 颗星，每赢一局得一颗星，输一局掉一颗星。
- 如果在段位 \(i\) 已经拥有 \(m\) 颗星，且再赢一局，则进入段位 \(i+1\)。若在当前段位已经拥有 \(0\) 颗星，且再输一局，则进入段位 \(i−1\)。
- 从一个段位进入下一个段位会清空之前段位的星，并获得 \(1\) 颗星。从一个段位到达上一个段位会清空之前段位的星，获得 \(m−1\) 颗星。如果当前段位已拥有 \(1\) 颗星，且再输一局，则当前段位拥有 \(0\) 颗星。
- 升星机制：每连赢 \(d\) 局之后会 \(+1\) 颗星，无上限。如果连赢 \(kd\) 局则会 \(+k\) 颗星。
- 玩家初始时从段位 \(1\) 的 \(1\) 颗星开始。
- 完成 \(n\) 局游戏后段位绝对不可能是 \(0\) 或者负整数，但中途可以出现此情况，我们认为这是游戏的一种结算机制。若最终段位为 \(0\) 或负整数，视为段位 \(1\)。
（以上规则基本与某多人社交游戏相同）
为了让问题更简单也更符合她的游戏体验，她告诉你 \(m=5\)。
她会给你一个长度为 \(n\) 的字符串 \(S=⋯\) 表示当天的游戏记录，其中 \(Si∈0,1,?\)，\(0/1\) 表示对局的输赢，\(?\) 表示她不记得对局情况了。她还会给你 \(d,B\) 两个自然数，分别表示升星需连续赢的对局数和总共赢的对局数。
输入格式
第一行两个正整数 \(d,B\)。
第二行一个长度为 \(n\) 的字符串，表示对局情况。
输出格式
一行一个正整数，表示根据智乃给出的对局记录所能够到达的最高段位。
数据范围
对于 \(100\%\) 的数据，\(n≤5000,B≤5000,d≤200\)。
| 测试点 | \(d=?\) | \(B=?\) | \(n=?\) |
|---|---|---|---|
| \(1\) | \(3\) | \(60\) | \(100\) |
| \(2\) | \(5\) | \(300\) | \(500\) |
| \(3\) | \(30\) | \(550\) | \(1000\) |
| \(4\) | \(55\) | \(3000\) | \(5000\) |
| \(5\) | \(55\) | \(4000\) | \(5000\) |
| \(6\) | \(10\) | \(4000\) | \(5000\) |
| \(7\) | \(8\) | \(3041\) | \(3500\) |
| \(8\) | \(3\) | \(3156\) | \(5000\) |
| \(9\) | \(150\) | \(4000\) | \(5000\) |
| \(10\) | \(150\) | \(4000\) | \(5000\) |
格式说明
输出时每行末尾的多余空格，不影响答案正确性
样例输入1
5 5
1111100
样例输出1
2
样例输入2
5 5
0011111
样例输出2
1
样例解释2
经过 \(7\) 次比赛后的段位和星数分别为：
- 段位 \(1\)，星数 \(0\)；
- 段位 \(−1\)，星数 \(4\)；
- 段位 \(−1\)，星数 \(5\)；
- 段位 \(1\)，星数 \(1\)；
- 段位 \(1\)，星数 \(2\)；
- 段位 \(1\)，星数 \(3\)；
- 胜利加一颗星，连续胜利 \(5\) 场再加一颗星，最终段位 \(1\)，星数 \(5\)。
因此最高的最终段位为 \(1\)。
样例输入3
5 20
100???01110000????0101??1000?????11110000101??100
样例输出3
1
Solution
这个题目有几个地方比较巧妙，不是很容易能想得到
初次做的时候很容易想到设计状态 \(dp_{i,j,k}\) 表示前 \(i\) 局，赢了 \(j\) 局，当前连胜 \(k\) 局的最高分数（把段位和星数结合考虑处理成分数，最后算答案的时候把分数重新换算成段位），转移也很好转移（这里不再展示），但是显然会 \(TLE\)，而且数组也开不下
首先将段位+星数转化为分数：1段0星即以下->0分，1段1星->1分，……
这里有个比较巧妙的地方——我们不要1段5星->5分，2段0星->6分，2段1星->7分，最好是1段5星（2段0星）->5分，2段1星->6分，这样更方便计算。但是问题是，这样对应怎么区分满星和0星（它们的分数都是 \(m\) 的倍数，即 \(5\) 的倍数）？
仔细思考一下，其实满星和0星是等效的，只不过如果最后一局赢了并且分数是 \(m\) 的倍数，说明是从 \(m-1\) 颗星升到的 \(m\) 星；最后一局输了并且分数是 \(m\) 的倍数，说明是从 \(1\) 星降到了 \(0\) 星。也就是说只需要看最后一局是输是赢，即可顺利区分满星和0星
这两种不同情况统一之后，问题就变得好思考一些了，不用管升段还是降段，只计算分数就好。
总共赢了 \(B\) 局，输了 \(n-B\) 局，初始分数是 \(1\) 分（1段1星），那么最终的分数就是 \(max\{1+B-(n-B)+最多连胜奖励, 0\}\)
问题转化为，给定一堆 \(?\) 可以选择 \(0/1\) ， 要求连续的 \(1\) 获得连胜奖励最多。
设第 \(i\) 段连续的 \(1\) 的长度是 \(len1_i\) ，要求的就是 \(max\{\Sigma_i{\lfloor \frac{len1_i}{d} \rfloor} \}\)
设 \(dp_{i,j,0/1}\) 表示前 \(i\) 局，赢了 \(j\) 局，当前这一局赢(\(1\))或者输(\(0\))，所获得的的连胜奖励
这一局输了的转移方程很好写：\(dp_{i,j,0}=max\{dp_{i-1,j,0},dp_{i-1,j,1}\}\)，肯定没有连胜，直接继承上一局的连胜奖励情况
这一局赢了如何转移呢？
比如以下这种情况：\(d=3\)，局面是\(1111111\)，显然这种情况会获得2分奖励。
我其实可以理解成：前 \(6\) 局，有两个 \(3\) 局连胜，获得 \(2\) 分奖励；
也可以理解成：后 \(6\) 局，有两个 \(3\) 局连胜，获得 \(2\) 分奖励；
甚至还可以理解成：前 \(3\) 局连胜，后 \(3\) 局连胜，获得 \(2\) 分奖励。
以上几种理解其实是等效的。换句话来说，只要保证你视为连胜的场次不相交，最终算出来的答案是一样的。
那么这就为我们赢了的情况提供了转移的思路
\[dp_{i,j,1}=max \begin{cases} max\{dp_{i-1,j-1,1},dp_{i-1,j-1,0}\}& 直接继承上一局的连胜情况\\ max\{dp_{i-d,j-d,1},dp_{i-d,j-d,0}\}+1& 视为当前的d局连胜(如果可以连胜d局)，获得1分奖励 \end{cases}\]最终的分数就是 \(max\{1+B-(n-B)+max\{dp_{n,B,0},dp_{n,B,1}\}, 0\}\)
最后把分数转化为段位，每 \(5\) 分是 \(1\) 段，不过如果分数是5的整数倍，就要看最后一局选的是赢还是输，根据之前说的判断方法就可以了
时间复杂度 \(O(nB)\)，完美通过此题
至此这道题目就解决了。
附上代码
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define N (5000+5)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
int d,B,n,m=5;
char s[N];
int dp[N][N][2];
bool may[N]; //may[]:当前位置有没有可能连胜了d局
int main(){
scanf("%d%d",&d,&B);
scanf("%s",s+1);
n=strlen(s+1);
memset(dp,-0x3f,sizeof(dp));
dp[0][0][0]=dp[0][0][1]=0;
int cnt=0;
for(int i=1;i<=n;i++){
if(s[i]=='0') cnt=0;
else{
cnt++;
if(cnt>=d){
may[i]=1;
}
}
}
for(int i=1;i<=n;i++){
int minj=min(i,B);
for(int j=0;j<=minj;j++){
if(s[i]=='0'){
dp[i][j][0]=max(dp[i][j][0],max(dp[i-1][j][0],dp[i-1][j][1]));
}
else if(s[i]=='1'){
if(j>=1) dp[i][j][1]=max(dp[i][j][1],max(dp[i-1][j-1][0],dp[i-1][j-1][1]));
if(j>=d&&i>=d&&may[i]) dp[i][j][1]=max(dp[i][j][1],max(dp[i-d][j-d][0],dp[i-d][j-d][1])+1);
}
else{
dp[i][j][0]=max(dp[i][j][0],max(dp[i-1][j][0],dp[i-1][j][1]));
if(j>=1) dp[i][j][1]=max(dp[i][j][1],max(dp[i-1][j-1][0],dp[i-1][j-1][1]));
if(j>=d&&i>=d&&may[i]) dp[i][j][1]=max(dp[i][j][1],max(dp[i-d][j-d][0],dp[i-d][j-d][1])+1);
}
}
}
int delta=0; //delta: 处理分数是m的倍数的情况
int maxx=max(dp[n][B][0],dp[n][B][1]);
int ans=max((B<<1)-n+maxx+1,0);
if(dp[n][B][0]<dp[n][B][1]&&ans%m==0) delta=-1;
ans=ans/m+1+delta;
if(ans==0) ans=1;
printf("%d\n",ans);
return 0;
}