1.区间dp--精妙状态设计与转移
https://codeforces.com/contest/2129/problem/D
dp[l][r][a][b]:
表示只考虑放置[l,r]区间内部的数,并且满足所有的s[l]~s[r]的条件,对l-1的贡献是a,对r+1的贡献是b的方案数
转移:
对于dp[l][r][a][b]来说,枚举第一个放置的数,比如说是k,如果k对l-1产生贡献,记lf=1,否则记录rf=1
然后放完k之后,之后放置的[l,k-1]区间内的数是一定不会对[k+1,r]区间内的数产生贡献,[k+1,r]对[l,k-1]也是同理
所以有:
dp[l][k-1][a][b]dp[k+1][r][a'][b']C[r-l][k-l]->dp[l][r][a+lf][b'+rf]
2.博弈论dp+按照贡献拆分求方案数
https://codeforces.com/contest/2140/problem/E2
首先就是考虑m==2的情况,那么Alice一定是想要最后的结果为1的,然后Bob一定是想要最后的结果为0
所以可以设计dp[i][j]表示当前的局面为i,并且还剩下j轮就结束比赛
状态转移可以用记忆化:
int ge(int u,int s){//删掉u的第s位后的值 int t1=u&po[s];//要减去的值 int t=u>>(s+1);int t2=t<<s;//int t3=t<<(s+1);return u-t1-t3+t2;
}
int dfs(int u,int s){if(dp[u][s]!=-1) return dp[u][s];if(!s){if(u==1) dp[u][s]=1;else dp[u][s]=0;return dp[u][s];}for(int i=0;i<=s;i++)if(st[i]){if((n-s)%2==1){dp[u][s]=max(dp[u][s],dfs(ge(u,i),s-1));//Alice想拿最大的局面}else{//Bob想要局面尽可能的小if(dp[u][s]==-1) dp[u][s]=dfs(ge(u,i),s-1);else{dp[u][s]=min(dp[u][s],dfs(ge(u,i),s-1));}}}return dp[u][s];
}
然后对于m<=1e6的情况该去如何计算?
还是用上面的二进制状态表示,枚举k(1<=k<=m)
1:表示a[i]>=k
0:表示a[i]<k
然后用dp[i][n-1]去求对于局面i而言,是否能取得最终结果>=k
对于每一次的k的方案数计算如下:
int ans=0;for(int i=0;i<po[n];i++) if(dp[i][n-1]==1){cnt[__builtin_popcount(i)]++;}for(int i=1;i<=m;i++)for(int j=1;j<=n;j++){//至少要有一个1ans+=qmi(i-1,n-j)*qmi(m-i+1,j)%mod*cnt[j]%mod;ans%=mod;}
然后为什么ans的值就是枚举的k的方案数总和呢?
首先ans就是所有可能局面最终留下来的值的总和
当k=1时,包含最终留下来的局面为:1 2 3 4 5 …… m
当k=2时,包含最终留下来的局面为: 2 3 4 5 …… m
当k=3时,包含最终留下来的局面为: 3 4 5 …… m
……
所以显而易见的是求所有值的总和正好是枚举的所有k的方案数的总和