)
AT_dp_j Sushi
首先有一个显然但重要的性质，就是盘子之间是没有区别的，比如1号盘子有2个寿司，3号盘子有3个寿司，和1号盘子有3个寿司，3号盘子有2个寿司的期望次数是相同的
这说明我们无需考虑每一个盘子具体有多少寿司，只需要考虑每种寿司数量的盘子个数，就是有0个寿司的盘子总数，有1个寿司的盘子总数，有2个寿司的盘子总数和有3个寿司的盘子总数
由于n只有300，所以我们可以暴力一点，把所有信息都记录在dp数组里
假设dp[p][i][j][k]表示当前有p个盘子上有0个寿司，有i个盘子上有1个寿司，j个盘子上有2个寿司，k个盘子上有3个寿司，这样的情况下的期望次数（即答案）
但是这样设状态的话空间就爆了，由于p+i+j+k=n，所以我们可以压掉p这一维，用n-i-j-k替代，当然压掉其他维也是可以的。
即设dp[i][j][k]表示有i个盘子上有1个寿司，j个盘子上有2个寿司，k个盘子上有3个寿司，这样的情况下的期望次数
然后考虑状态转移方程：
如果选到了0个寿司的盘子的话，那么没有盘子的寿司数量发生变化，概率为(n-i-j-k)/n，所以这部分的期望次数是
如果选到了1个寿司的盘子的话，那么i少了1，也就是1个寿司的盘子数量少了1，这样的概率是i/n，所以这部分的期望次数是
如果选到了2个寿司的盘子的话，那么j少了1，i多了1，也就是2个寿司的盘子数量少了1，然后这个盘子变成1个寿司，所以一个寿司的盘子数量多了1，概率为j/n，这部分拿到期望次数是
如果选到了3个寿司的话，同理，这部分期望次数是
由于只会选到这4种情况，所以这种情况下的期望次数就是这四者的和+1，也就是说
左右两边都有dp[i][j][k]，合并同类项变成可递推的形式：
然后注意转移顺序，因为(i,j,k)从(i,j+1,k-1)转移，既然要保证算(i,j,k)时(i,j+1,k-1)已计算出，所以必须先按照k从小到大循环。因为(i,j,k)也从(i+1,j-1,k)转移，所以第二层是j从小到大循环，所以枚举顺序是：k->j->i
最终答案就是最初情况下，假设1个寿司的盘子个数cnt1，2个寿司的盘子个数cnt2，3个寿司的盘子个数cnt3，那么答案是dp[cnt1][cnt2][cnt3]
代码如下：
#include<bits/stdc++.h> using namespace std; #define _for(i,a,b) for(int i = (a) ; i <= (b) ; i ++) #define for_(i,a,b) for(int i = (a) ; i >= (b) ; i --) const int maxn = 3e2 + 10; double dp[maxn][maxn][maxn]; int n; int a[maxn]; int cnt[maxn]; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin >> n; _for(i , 1 , n) { cin >> a[i]; cnt[a[i]] ++; } _for(k , 0 , n){ _for(j , 0 , n){ _for(i , 0 , n){ if(i + j + k == 0) continue; if(i) dp[i][j][k] += (i * dp[i - 1][j][k]) / (i + j + k); if(j) dp[i][j][k] += (j * dp[i + 1][j - 1][k]) / (i + j + k); if(k) dp[i][j][k] += (k * dp[i][j + 1][k - 1]) / (i + j + k); dp[i][j][k] += n * 1.0 / (i + j + k); } } } printf("%.9lf",dp[cnt[1]][cnt[2]][cnt[3]]); return 0; }AT_dp_k Stones
这是一个明显的博弈论，假设dp[i]表示剩余i块石头时，当前操作者的胜负
注意是当前操作者，不一定是先手后手
那么显然，如果我能取到任意一种情况，让对手，也就是上一轮的操作者必败，那么我必胜
那么我们发现，如果存在dp[i-a[j]]=0，那么dp[i]=1
最终答案是dp[k]，也就是一块石子都没动时的操作者，也就是先手胜负
代码如下：
#include<bits/stdc++.h> using namespace std; #define _for(i,a,b) for(int i = (a) ; i <= (b) ; i ++) #define for_(i,a,b) for(int i = (a) ; i >= (b) ; i --) const int maxm = 110; const int maxn = 1e5 + 10; int dp[maxn]; int n,m; int a[maxn]; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin >> n >> m; _for(i , 1 , n) cin >> a[i]; dp[0] = 0; _for(i , 1 , m) { _for(j , 1 , n){ if(i - a[j] >= 0 && dp[i - a[j]] == 0) { dp[i] = 1; break; } } } cout << (dp[m]?"First":"Second"); return 0; }AT_dp_l Deque
这是我认为非常好的一个题，有两种做法
第一种是区间DP，首先考虑先手希望x-y大，后手希望x-y小，那么说明先手希望x尽可能大，因为和固定，x越大，y越小，同理，后手希望y尽可能大，也就是说两者都希望自己的得分尽可能多
那么假设dp[l][r]表示当前操作者在[l,r]取得的最大分数，由于这一次的操作者和上一次操作者相反，那么可以得出方程：
就是用总和减去对手的最小得分，就是自己的最大得分
正常来讲这道题到这里就结束了，也可以通过，但是这个dp的空间复杂度是可以优化的
因为一个区间的信息包括：左端点，右端点，区间长度，知其二可以求另一个，这里我们记录的信息是左右端点，但是转移是从小区间转移到大区间，所以在区间长度上存在顺序：从小到大
那么我们考虑把dp状态重新表示一下：
dp[len][l]表示以l为左端点，区间长度为len的当前操作者最大得分，所以方程可以改写成这样：
发现len永远从len-1转移，那么我们只需要每次枚举l之前把dp[len-1]的所有值都存在一个pre数组里，每次转移只需要在pre[l]和pre[l+1]取min
这样空间复杂度就优化到了O(n)
代码如下：
*#include<bits/stdc++.h> using namespace std; #define int long long #define _for(i,a,b) for(int i = (a) ; i <= (b) ; i ++) #define for_(i,a,b) for(int i = (a) ; i >= (b) ; i --) const int maxn = 3e3 + 10; int dp[maxn]; int pre[maxn]; int n,sum[maxn]; int a[maxn]; signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin >> n; _for(i , 1 , n) cin >> a[i]; _for(i , 1 , n) dp[i] = a[i],sum[i] = sum[i - 1] + a[i]; _for(len , 2 , n){ _for(l , 1 , n){ pre[l] = dp[l]; } for(int l = 1 ; l + len - 1 <= n ; l ++){ int r = l + len - 1; dp[l] = sum[r] - sum[l - 1] - min(pre[l],pre[l + 1]) ; } } cout << 2 * dp[1] - sum[n]; return 0; }第二种做法：贪心
如果存在三个数满足“峰形”，即：
那么我们发现，这三个数的贡献和是一定的
假设轮到A选，他会选a[i]或a[i+2]，那么轮到B时，他一定会选择a[i+1]，然后A选a[i]和a[i+2]的另一个
所以这三个数对于A的贡献是a[i]+a[i+2]-a[i+1]，所以三个数可以缩成一个数，同理，缩完之后的数还可以再缩，最终使得整个数组变成一个“谷形”，就是先递减后递增：因为不存在任何的峰，所以这就变成了一个贪心问题，两边选，哪个大选哪个
至于这个缩的过程，我们可以用一个栈模拟，每次检测栈顶的三个元素，如果满足峰形，就合并成一个元素
代码如下：
#include<bits/stdc++.h> using namespace std; #define int long long #define _for(i , a , b) for(int i = a ; i <= b ; i ++) #define for_(i , a , b) for(int i = a ; i >= b ; i --) const int maxn = 3e3 + 10; int a[maxn]; int n; int tp; bool check(){ if(tp < 3) return 0; if(a[tp] <= a[tp - 1] && a[tp - 2] <= a[tp - 1]) return 1; return 0; } signed main(){ cin >> n; _for(i , 1 , n) { int x; cin >> x; a[++ tp] = x; while(check()){ int x = a[tp]; -- tp; int y = a[tp]; -- tp; int z = a[tp]; -- tp; a[++ tp] = x + z - y; } } int lidx = 1,ridx = tp; int lans = 0,rans = 0; int vix = 0; while(lidx <= ridx){ int num; if(a[lidx] < a[ridx]) { num = a[ridx]; ridx --; } else{ num = a[lidx]; lidx ++; } if(!vix) lans += num; else rans += num; vix ^= 1; } cout << lans - rans; return 0; }
