Digital DP
template
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[20];
ll dp[20][state];
ll dfs(int pos, /*state变量*/, bool lead/*前导零*/, bool limit/*数位上界变量*/)
{
if(pos == -1) return 1;
if(!limit && !lead && dp[pos][state] != -1) return dp[pos][state];
int up = limit ? a[pos] : 9;
ll ans = 0;
for(int i = 0; i <= up; i++)
{
if() ...
else if()...
ans += dfs(pos - 1, /*状态转移*/, lead && i == 0, limit && i == a[pos]);
}
if(!limit && !lead) dp[pos][state] = ans;
return ans;
}
ll solve(ll x)
{
int pos = 0;
while(x)
{
a[pos++] = x % 10;
x /= 10;
}
return dfs(pos - 1/*从最高位开始枚举*/, /*一系列状态 */, true, true);
}
int main()
{
ll le, ri;
memset(dp, -1, sizeof(dp));
while(~scanf("%lld%lld", &le, &ri))
{
printf("%lld\n", solve(ri) - solve(le - 1));
}
}
<div STYLE="page-break-after: always;"></div>
Digit sum
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[20000], digit;
ll dp[2000][2000];
ll ans[10], ans2[10];
ll dfs(int pos, /*state变量*/int cnt, bool lead/*前导零*/, bool limit/*数位上界变量*/)
{
if(pos == -1)
return cnt;
if(!limit && !lead && dp[pos][cnt] != -1) return dp[pos][cnt];
int up = limit ? a[pos] : 9;
ll ans = 0;
for(int i = 0; i <= up; i++)
{
int ncnt = cnt + (i == digit);
if(lead && i == 0 && digit == 0)
ncnt = 0;
ans += dfs(pos - 1, /*状态转移*/ncnt, lead && i == 0, limit && i == a[pos]);
}
if(!limit && !lead) dp[pos][cnt] = ans;
return ans;
}
void solve(ll x)
{
int pos = 0;
while(x)
{
a[pos++] = x % 10;
x /= 10;
}
for(int i = 0; i <= 9; i++)
{
digit = i;
ans[i] += dfs(pos - 1/*从最高位开始枚举*/, 0/*一系列状态 */, true, true);
}
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll le, ri;
memset(dp, -1, sizeof(dp));
while(cin>>le>>ri)
{
if(!le && !ri) break;
if(le > ri)
swap(le, ri);
memset(ans, 0, sizeof(ans));
solve(ri);
memcpy(ans2, ans, sizeof(ans));
memset(ans, 0, sizeof(ans));
solve(le - 1);
for(int i = 0; i <= 9; i++)
{
cout<<ans2[i] - ans[i];
if(i != 9)
cout<<" ";
}
cout<<endl;
}
}
<div STYLE="page-break-after: always;"></div>
Non-falling number
/*
不降数的个数应该与位数以及最高位数字有关
状态:f[i][j]表示一共有i位，且最高位为j的不降数的个数
j K X X ... X
i i-1
转移:因为最高位已经固定为j,所以假定第i-1位是k，根据不降数
定义k>=j,所以f[i][j] = Σ(k=j~9)f[i-1][k]
即f[i][j] = f[i-1][j+1]+f[i-1][j+2]+...+f[i-1][9]
因为是从高位往低位算，所以我们需要做预处理
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 12;
int a[N];//把整数每一位抠出来
int f[N][N];//f[i][j]表示一共i位，且最高位是j的不降数的个数
void init()
{
for(int i = 0;i <= 9; i++) f[1][i] = 1;//一位数
for(int i = 2; i < N; i++)//阶段:枚举位数
for(int j = 0; j <= 9; j++)//状态：枚举最高位
for(int k = j; k <= 9; k++)//决策:枚举次高位
f[i][j] += f[i - 1][k];
}
int calc(int n)
{
if(!n)//特判,n=0直接返回1
return 1;
int cnt = 0;
while(n)
a[++cnt] = n % 10,n /= 10;
int res = 0, last = 0;//last表示上一位数字
for(int i = cnt; i; i--)
{
int now = a[i];//表示当前位
for(int j = last; j < now; j++)//枚举当前位可填入的数字
res += f[i][j];
if(now < last)break;//若小break
last = now;
if(i == 1) res++;//特判，走到了a1(原数)
}
return res;
}
int main()
{
init();
int l, r;
while(cin>>l>>r)
{
cout<<calc(r) - calc(l - 1)<<endl;
}
return 0;
}
<div STYLE="page-break-after: always;"></div>
P1836 Number of pages
//求1-n所有数字单个数字的和
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[20];
ll dp[200][200];
ll dfs(int pos, /*state变量*/ll sum, bool lead/*前导零*/, bool limit/*数位上界变量*/)
{
if(pos == -1) return sum;
if(!limit && !lead && dp[pos][sum] != -1) return dp[pos][sum];
int up = limit ? a[pos] : 9;
ll ans = 0;
for(int i = 0; i <= up; i++)
{
ll tmp = sum + i;
if(lead && i == 0)
tmp = 0;
ans += dfs(pos - 1, tmp, lead && i == 0, limit && i == a[pos]);
}
if(!limit && !lead) dp[pos][sum] = ans;
return ans;
}
ll solve(ll x)
{
int pos = 0;
while(x)
{
a[pos++] = x%10;
x /= 10;
}
return dfs(pos - 1/*从最高位开始枚举*/, 0/*一系列状态 */, true, true);
}
int main()
{
memset(dp, -1, sizeof(dp));
ll n;
cin>>n;
cout<<solve(n)<<endl;
}
<div STYLE="page-break-after: always;"></div>
P2602 [ZJOI2010] Digital count
//0-9 在 [a,b]中出现了多少次。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[20];
ll dp[20][20][2], digit;
ll ans1[20], ans2[20];
ll dfs(int pos, bool lead, bool limit, int cnt)
{
if(pos==-1) return cnt;
if(!limit && !lead && dp[pos][cnt][digit != 0] != -1) return dp[pos][cnt][digit != 0];
int up = limit ? a[pos] : 9;
ll ans = 0;
for(int i = 0; i <= up; i++)
{
int tmp = cnt + (i == digit);
if(lead && digit == 0 && i==0) tmp = 0;
ans += dfs(pos - 1, lead && i == 0, limit && i == a[pos], tmp);
}
if(!limit && !lead) dp[pos][cnt][digit != 0] = ans;
return ans;
}
void solve(ll x)
{
int pos = 0;
while(x)
{
a[pos++] = x % 10;
x /= 10;
}
for(int i = 0; i <= 9; i++)
{
digit = i;
ans1[i] += dfs(pos - 1, true, true, 0);
//cout<<ans1[i]<<" ";
}
}
int main()
{
ll le, ri;
memset(dp, -1, sizeof(dp));
while(~scanf("%lld%lld", &le, &ri))
{
solve(ri);
memcpy(ans2, ans1, sizeof(ans1));
memset(ans1, 0, sizeof(ans1));
solve(le - 1);
for(int i = 0; i <= 9; i++)
cout<<ans2[i] - ans1[i]<<" ";
cout<<endl;
}
}
<div STYLE="page-break-after: always;"></div>
P2657 [SCOI2009] windy num
/*
不含前导零且相邻两个数字之差至少为 2 的正整数被称为 windy 数。windy 想知道，
在 a和 b 之间，包括 a 和 b ，总共有多少个 windy 数？
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[20];
ll dp[20][20];//不同题目状态不同
ll dfs(int pos, /*state变量*/int pre, bool lead/*前导零*/, bool limit/*数位上界变量*/)//不是每个题都要判断前导零
{
if(pos == -1) return 1;
if(!limit && !lead && dp[pos][pre] != -1) return dp[pos][pre];
int up = limit ? a[pos] : 9;
ll ans = 0;
for(int i = 0; i <= up; i++)
{
int delta = abs(pre - i);
if(delta < 2&& !lead) continue;
// if(i==up&&limit)ans+=dfs(pos-1,i,false,true);
// else ans+=(i||!lead)?dfs(pos-1,i,false,false):dfs(pos-1,i,true,false);
ans += dfs(pos-1, i,(lead && !i), limit && i == a[pos]);
}
if(!limit && !lead) dp[pos][pre] = ans;
return ans;
}
ll solve(ll x)
{
int pos = 0;
while(x)
{
a[pos++] = x % 10;
x /= 10;
}
return dfs(pos - 1, 0, true, true);
}
int main()
{
ll le, ri;
memset(dp, -1, sizeof(dp));
while(~scanf("%lld%lld", &le, &ri))
{
printf("%lld\n", solve(ri) - solve(le - 1));
}
}
<div STYLE="page-break-after: always;"></div>
P4124 [CQOI2016] Mobile phone number
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[20];
ll dp[20][20][20][4][2][2];
//第i为,上一位,上上一位,是否3个连续,是否有4,是否有8
ll dfs(int pos, int pre, int ppre, bool state, bool _4, bool _8, bool limit/*数位上界变量*/)
{
if(_4 && _8) return 0;
if(pos == -1) return state;
if(!limit && dp[pos][pre][ppre][state][_4][_8] != -1) return dp[pos][pre][ppre][state][_4][_8];
int up = limit ? a[pos] : 9;
ll ans = 0;
for(int i = 0; i <= up; i++)
{
ans += dfs(pos - 1, i, pre, state || (i == pre && i == ppre), (_4 || (i == 4)), _8 || (i == 8), limit && (i == a[pos]));
}
if(!limit) dp[pos][pre][ppre][state][_4][_8] = ans;
return ans;
}
ll solve(ll x)
{
int pos = 0;
while(x)
{
a[pos++] = x % 10;
x /= 10;
}
if(pos!=11)return 0;
ll ans = 0;
for(int i = 1; i <= a[pos - 1]; i++)
{
ans += (long long)dfs(pos - 2, i, 0, 0, i == 4, i == 8, i == a[pos - 1]);
}
return ans;
}
int main()
{
ll le, ri;
memset(dp, -1, sizeof(dp));
while(~scanf("%lld%lld", &le, &ri))
{
printf("%lld\n", solve(ri) - solve(le - 1));
}
}
//10000000000 53628881996
//2186241614
<div STYLE="page-break-after: always;"></div>
P6218 [USACO06NOV] Round Numbers S
//圆数：二进制0的数目不小于1，区间 [l,r][l,r] 中有多少个「圆数」
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[33];
ll dp[33][66];
ll dfs(int pos, int state, bool lead, bool limit)
{
if(pos == -1) return state >= 32;
if(!limit && !lead && dp[pos][state] != -1) return dp[pos][state];
int up = limit ? a[pos] : 1;
ll ans = 0;
for(int i = 0; i <= up; i++)
{
if(lead && i == 0) ans += dfs(pos - 1, state, lead, limit && i == a[pos]);
else ans += dfs(pos - 1, state + (i == 0 ? 1 : -1), lead && i == 0, limit && i == a[pos]);
}
if(!limit && !lead) dp[pos][state] = ans;
return ans;
}
ll solve(ll x)
{
int pos = 0;
while(x)
{
a[pos++] = x & 1;
x >>= 1;
}
return dfs(pos - 1/*从最高位开始枚举*/, 32/*一系列状态 */, true, true);
}
int main()
{
ll le, ri;
memset(dp, -1, sizeof(dp));
while(~scanf("%lld%lld", &le, &ri))
{
printf("%lld\n", solve(ri) - solve(le - 1));
}
}
<div STYLE="page-break-after: always;"></div>
Interval DP
template
/*
核心代码
memset(dp, 0, sizeof(dp)) //初始dp数组
for(int len = 2; len <= n; len++){ //枚举区间长度
for(int i = 1; i < n; ++i){ //枚举区间的起点
int j = i + len - 1; //根据起点和长度得出终点
if(j > n) break; //符合条件的终点
for(int k = i; k <= j; ++k) //枚举最优分割点
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
//状态转移方程
}
}
*/
#include<iostream>
using namespace std;
const int N = 310;
int s[N], f[N][N];
int n;
int main()
{
cin>>n;
for(int i = 1; i <= n; i++)
{
cin>>s[i];
s[i] += s[i - 1];
}
for(int len = 2; len <= n; len++)
{
for(int i = 1; i + len - 1 <= n; i++)
{
int l = i, r = i + len - 1;
f[l][r] = 1e8;
for(int k = l; k < r; k++)
{
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
}
}
}
cout<<f[1][n];
}
<div STYLE="page-break-after: always;"></div>
ICPC Beijing 2017 J, Pangu and Stones
/*
有n堆石子,每堆有ai个,给定L,R,相邻的连续[L,R]堆石子可以合并成一堆，
代价是这些堆中石子数量之和
求把n堆石子合并成一堆的最小代价，情况不存在输出0
g[l][r][k] l~r合并成k堆的最小代价和
k>=2 g[l][r][k] = min(g[l,m,1]+g[m+1,r,k-1]); 枚举分界点改用dp去做
k=1 min(g[l,r,k]+石子数量和)
思路：
可以把合并所有石头的过程拆分成几个子步骤，首先合并连续的一些，然后再合并连续的一些，大区间的结果可以由小区间推出，所以就从小区间开始考虑，逐步推向大区间，可以用 dp[i][j][k] 表示区间 [i,j] 分成 k 堆得最小代价，对于固定的一个区间，肯定是取所有情况的最小值，最后答案是 dp[1][n][1] ，
注意边界处理，包括刚开始的初始化。
然后就是代码处理中的一些细节了。
首先将所有的 f[i][j][k] 置为 INF 。
然后对于所有的初始状态（即 f[i][j][j-i+1] ）都置为 0 。
因为区间 [i,j] 内本身就有 j−i+1 个元素，所以这些元素本身就这么多堆，是不需要花费代价去划分的。这就是我所说的初始状态。
然后就是合并区间了，区间合并一般都是小区间开始合并到大区间，我们这里也不例外（记忆化搜索的话就得反着来了）。
对于一个区间 [l,r] ，它要么是直接合并成一堆，要么是若干个区间拼接到一起。所以我们这里分情况讨论：
直接合并
如果区间 [l,r] 直接合并，那么合并成一堆的最小代价应该是 f[l][r][1] 。
那么对于区间 [l,r] ，我一定可以将其拆分成两个区间 [l,i] 和 [i+1,r] ，其中左区间有 j 个元素，右区间有 1 个元素，并且满足 L≤j+1≤R 。
于是我们可以从 l~r−1 枚举 i ，从 L−1~R−1 枚举 j ，
则 f[l][r][1]=min(f[l][i][j]+f[i+1][r][1])+sum[r]−sum[l−1] 。（这里 sum[r]−sum[l−1] 表示区间 [l,r] 范围内的石子数量之和）
区间拼接
这里讲的区间拼接其实就是对于两个区间 [l,j] 和 [j+1,r] ，假设他们分别有 i−1 堆和 1 堆石子，那么这个区间总共有 i 堆石子。
区间拼接就不需要考虑合并了。
所以对于区间 [l,r] 包含 i 堆石子的情况，它对应状态 f[l][r][i] ，那么它总能拆分成两个状态（f[l][j][i−1] 和 f[j+1][r][1] ，其中 l≤j<r）的拼接。
可以推导出状态转移方程为： f[l][r][i]=min(f[l][j][i−1]+f[j+1][r][1]) ，其中 2≤i≤len,l≤j<r 。
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
const int inf = 1 << 29;
int n, L, R, sum[N], a[N], f[N][N][N];
int main()
{
while(cin>>n>>L>>R)
{
for(int i = 1; i <= n; i++)
{
cin>>a[i];
sum[i] = sum[i - 1] + a[i];
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
for(int k = 1; k <= n; k++)
f[i][j][k] = inf;
for(int l = 1; l <= n; l++)
for(int r = l; r <= n; r++)
f[l][r][r - l + 1] = 0;
for(int len = 1; len <= n; len++)
{
for(int l = 1; l + len -1 <= n; l++)
{
int r = l + len - 1;
for(int i = l; i < r; i++)//直接合并
{
for(int j = L - 1; j < R; j++)//左区间j个元素,右区间1个元素
{
f[l][r][1] = min(f[l][r][1], f[l][i][j] + f[i + 1][r][1] + sum[r] - sum[l - 1]);
}
}
for(int i = 2; i < len; i++)//区间拼接 ,设该区间总共i堆石子
{
for(int j = l; j < r; j++)
{
f[l][r][i] = min(f[l][r][i], f[l][j][i - 1] + f[j + 1][r][1]);
}
}
}
}
if(f[1][n][1] == inf) cout<<0<<endl;
else cout<<f[1][n][1]<<endl;
}
return 0;
}
<div STYLE="page-break-after: always;"></div>
Parenthesis sequence
#include<bits/stdc++.h>
using namespace std;
int f[510][510];
int n;
char str[510];
//f[i][j]表示si,si+1...sj种最长的合法子序列长度
/*
转移：
1.f[i][j] = max(f[i][j],f[i+1][j])
2.f[i][j] = max(f[i][j],f[i][j-1])
3.(A),[A]:如果si和sj匹配，f[i][j]=max(f[i][j],f[i+1][j-1]+2)
4.AB:枚举AB的分界线k,f[i][j]=max(f[i][j],f[i][k]+f[k+1][j])
前面一个合法序列A和后面一个合法序列B
其实1,2不用考虑，为什么呢？
因为4枚举分界点，包含了1,2
*/
int main()
{
cin>>n>>(str + 1);
memset(f, 0, sizeof(f));
for(int i = 1; i < n; i++)//枚举区间长度
{
for(int j = 1; j <= n - i; j++)//左端点
{
if((str[j] == '(' && str[j + i] ==')') || (str[j] == '[' && str[j + i] == ']'))
f[j][j + i] = f[j + 1][j + i - 1] + 2;
for(int k = j; k < j + i; k++)
{
f[j][j + i] = max(f[j][j + i],f[j][k] + f[k + 1][j + i]);
}
}
}
cout<<f[1][n]<<endl;
return 0;
}
/*
10
]]][()]])[
4
*/
<div STYLE="page-break-after: always;"></div>
Stone merging
//石子合并Ⅱ
#include<bits/stdc++.h>
using namespace std;
/*
圆上一共有n条边，每次合并都要用掉一条边
最后一定有一条边没用，我们枚举哪条边没用
剩下又变成链上问题了
时间复杂度O(n^4)
能否优化？
考虑一条长度为2n的链，是由两个a数组接起来的，
也就是说，>n的位置i对应了原来的第i-n堆石子
时间复杂度O(n^3)
*/
int n, a[501 * 2], f[501][501], s[501];
int main()
{
cin>>n;
for(int i = 1; i <= n; i++)
{
cin>>a[i];
a[i + n] = a[i];
}
memset(f, 127, sizeof(f));
n = n * 2;
for(int i = 1; i <= n; i++)
{
s[i] = s[i - 1] + a[i];
}
for(int i = 1; i <= n; i++) f[i][i] = 0;
for(int i = 1; i < n; i++)
{
for(int j = 1; j <= n - i; j++)
{
for(int k = j; k < j + i; k++)
{
f[j][j + i] = min(f[j][j + i], f[j][k] + f[k + 1][j + i] + s[j + i] - s[j - 1]);
}
}
}
int ans = 1 << 30;
for(int i = 1; i <= n / 2; i++)
{
ans = min(ans, f[i][i + n / 2 - 1]);
}
cout<<ans<<"\n";
return 0;
}
/*
abcabcabc
abcabc
*/
<div STYLE="page-break-after: always;"></div>
Probability DP
summary
——————————————小小总结QAQ——————————————
有这样一类问题，对于任意状态A，已知
①状态A所有后继状态
②设从状态A转移到后继状态B的概率P(A,B),则ΣB是A的后继状态P(A,B)=1
③从状态A转移到后继状态B的花费是W(A,B)
求解：从起始状态S到终止状态T的期望花费
求解这类问题的基本模式是：设E(A)表示从状态A到终止状态T的期望花费
初值：E(T) = 0;
那么可以得到转移公式:
E(A) = Σ(Bi是A的后继状态)P(A,B)*(E(Bi)+W(A,Bi))
我们可以把通过倒推(终点到起点,推出起点期望)
当转移关系不成环时,状态转移是线性的,可按拓扑排序递推求解
当转移关系成环时,列出所有状态转移方程,使用高斯消元解决
eg1.
给定一个起点是1,终点为n的有向无环图。
到达每一个顶点时,如果有k条离开该点的道路，可以选择任意一条道路离开该点
并且走向每条路的概率为1/k。
问你从1出发走到n的路径期望总长度是多少
dp[i] = Σ(j是i的后继状态)(dp[j]+w[i][j])*(1/k)
这题的终点很明确,那就是走到n即停止,对于期望DP,我们
一般采用逆序的方式来定义,即考虑当前状态到终点的期望代价
dp[i]为从i出发走到终点n的路径期望总长度
eg2.
有n个人排成一列,每一秒队伍最前面的人有p的概率走上电梯(一旦走上电梯就会一直在电梯上)
或者有1-p的概率不动,问T秒后,电梯上的人数期望
dp[i][j]:前i秒，电梯上有j个人的概率
dp[0][0] = 1;
dp[i+1][j+1] = dp[i][j]p;
dp[i+1][j] = dp[i][j](1-p);
eg3.
给定一个序列,一些位置未确定(是o与x的几率各占50%),对于一个ox序列，
连续a长度的o会得到a^2的收益,请问最终得到的序列的期望收益的多少?
观察到(a+1)2-a2 = 2a+1
根据期望的线性性质,我们可以分别计算出每一个字符的贡献
设l(i)表示以i结尾的极大连续o的长度的期望
设第i个字符为s，那么有三种情况:
ooo?o
↑
l[4] = 1/24+1/20 = 2
1.s = o,对答案的贡献l[i-1]2+1,l[i] = l[i-1]+1;
2.s = x,对答案贡献0,l[i] = 0;
3.s = ?,对答案贡献(l[i-1]2+1)/2,l[i] = (l[i-1]+1)/2
对于每个字符对答案的贡献是一个长度为a的一次多项式(2a+1)
对于期望的性质可知E(2a+1) = 2E(a)+1
所以计算连续o的长度的期望,即可求得序列的期望收益
eg3'.
给定一个序列,每个位置为o的几率为pi,为x的几率为1-pi,对于一个ox序列
连续a长度的o会得到a^3的收益，问最终得到的ox序列的期望收益是多少?
(a+1)^3 - a^3 = 3a^2+3a+1
我们分别计算每一个字符的贡献,注意E(a2)≠E(a)2,所以我们还有计算
以i为几位的极大连续o的长度的平方的期望
定义l1(i)表示:以i为结尾的极大连续o的长度的期望
定义l2(i)表示:以i为结尾的极大连续o的长度的平方的期望
计算l1和l2即可得到序列期望收益
设第i个字符为s，那么有三种情况:
1.s = o,对答案的贡献3l2(i-1)+3l1(i-1)+1,l[i] = l[i-1]+1
2.s = x,对答案贡献0,l[i] = 0;
3.s = ?,对答案贡献(3l2(i-1)+3l1(i-1)+1)/2,l[i] = (l[i-1]+1)/2
总结:
计算期望有几种基本的思路:
①计算从当前状态到终止状态的期望。将每个状态的期望值写成状态转移式，
终止状态的期望值往往是已知的
②利用期望的线性性质：E(x+y) = E(x)+E(y)。计算部分对整体的贡献。
最后两个例题就是根据期望的线性性质来计算答案的例子.当状态数量过大或难以表示时，就考虑分离变量的方法
③算出每个状态的出现概率，进而算出每个状态对答案的期望贡献
列出状态的概率转移式，起始状态的出现概率为1.
若状态是无环的则利用刷表法正向地推出每个状态的出现概率;
若有环,则列出所有状态的转移方程，将概率看作未知量,解线性方程即可
<div STYLE="page-break-after: always;"></div>
P4550 Collect stamps
//倒推+第n天完成的期望次数
#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
double num[N], ans[N];
int main()
{
int n;
cin>>n;
num[n] = 0, ans[n] = 0;
for(int i = n - 1; i >= 0; i--)
{
//num[i] = (double)(num[i]+1)*(i*(1.0)/n)+(num[i+1]+1)*((n-i)*(1.0)/n);
num[i] = (((num[i + 1]) * ((n - i) * (1.0) / n)) + 1) / (1 - (i * (1.0) / n));
}
for(int i = n - 1; i >= 0; i--)
{
//ans[i] = (double)(ans[i]+num[i]+1)*((1.0)*i/n)+(ans[i+1]+num[i+1]+1)*((1.0)*(n-i)/n);
ans[i] = (ans[i + 1] * (n - i) * (1.0) / n + num[i] * (i * 1.0) / n + num[i + 1] * (n - i) * (1.0) / n + 1)/(1 - i * 1.0 / n);
}
printf("%.2f\n",ans[0]);
return 0;
}
<div STYLE="page-break-after: always;"></div>
walk
/*
题意：
蜗蜗的世界里有 n 个城市，城市之间通过 m 条单向高速公路连接，
初始他在 1 号城市。蜗蜗想去 n 号城市游玩，假设现在他在 x 号城市，
他会等概率地选择从 x 出发的高速公路中的一条走过去。如果没有任何从 x 号城里出发的高速公路，他就只能留在原地了。
蜗蜗会一直走直到他无路可走。
请问蜗蜗有多大的概率能够走到 n 号城市。
每行两个整数 x,y(1≤x<y≤n) 描述一条从 x 号城市到 y 号城市的高速公路。
输出：
相对误差或绝对误差在eps = 1e-6 内即为正确。
关于相对误差和绝对误差：
绝对误差：你求的是a，正确答案是b，那绝对误差|b-a|
相对误差：|b-a|/max(1,a)(误差占答案的百分比)
思路：
用f[x]表示能走到x号城市的概率,f[1]=1;
考虑从x号城市出发的到y号城市的高速公路，通过下号城市走到y号城市的概率有多大呢？
f[y]+=f[x]/d[x],其中d[x]表示从x号城市出发的高速公路一共有多少条
能走到y号城市的概率：
f[y] = Σ(x∈pre(y))f[x]/d[x]
pre(y)表示所有连接到y号城市的高速公路的起点的集合
时间复杂度O(n+m)
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n,m;
std::vector<int>edge[N];
double f[N];
int main()
{
cin>>n>>m;
for(int i = 1; i <= m; i++)
{
int x, y;
cin>>x>>y;
edge[x].push_back(y);
}
memset(f, 0, sizeof(f));
f[1] = 1;
for(int i = 1; i <= n; i++)
{
int sz = edge[i].size();
for(auto j : edge[i])
{
f[j] += f[i] / sz;
}
}
printf("%.10f\n", f[n]);
return 0;
}
<div STYLE="page-break-after: always;"></div>
walk2
/*
蜗蜗的世界里有 n 个城市，城市之间通过 m 条单向高速公路连接，初始他在 1 号城市。蜗蜗想去 n 号城市游玩，假设现在他在 x 号城市，他会等概率地选择从 x 出发的高速公路中的一条走过去。如果没有任何从 x 号城里出发的高速公路，他就只能留在原地了。蜗蜗会一直走直到他无路可走。
请问蜗蜗有多大的概率能够走到 n 号城市。
一行一个数表示蜗蜗能够走到 n 号城市的概率。
由于答案是分数，请输出答案 mod 1e9+7。
每行两个整数 x,y(1≤x<y≤n) 描述一条从 x 号城市到 y 号城市的高速公路。
最简分数a/b mod p 的意思是找到整数c使得 bc ≡ a(mod p)
a/b = c
a = bc
a%p == bc%p
由于p是质数，根据费马小定理，b^(p-1)≡ 1(mod p),也就是说有 b^(p-2) ≡ b^(-1)(mod p),过程中所有
的a/b mod p的操作都可以用a*b^(p-2) mod p代替
b^(p-2)mod p可以用ksm求
能走到y号城市的概率f[y] = Σ(x∈pre(y))f[x]*d[x]^(p-2) mod p
一次ksm时间复杂度log(p)
所以最终时间复杂度O(n+mlog(p))
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1010;
const int p = 1e9 + 7;
int n,m;
std::vector<int>edge[N];
int f[N];
int ksm(int a, int b)
{
int ans = 1,base = a;
while(b)
{
if(b & 1)
ans = (ans * base) % p;
base = (base * base) % p;
b >>= 1;
}
return ans;
}
signed main()
{
cin>>n>>m;
for(int i = 1; i <= m; i++)
{
int x, y;
cin>>x>>y;
edge[x].push_back(y);
}
memset(f, 0, sizeof(f));
f[1] = 1;
for(int i = 1; i < n; i++)
{
int sz = edge[i].size();
for(auto j : edge[i])
{
f[j] += f[i] * ksm(sz, p - 2);
f[j] %= p;
}
}
cout<<f[n]<<endl;
return 0;
}
<div STYLE="page-break-after: always;"></div>
walk3
/*
题意：
蜗蜗的世界里有 n 个城市，城市之间通过 m 条单向高速公路连接，初始他在 1 号城市。蜗蜗想去 n 号城市游玩，假设现在他在 x 号城市，他会等概率地选择从 x 出发的高速公路中的一条走过去。
如果没有任何从 x 号城市出发的高速公路，他就只能留在原地了。蜗蜗会一直走直到他走到 n 号城市。
请问蜗蜗期望经过多少条高速公路能够走到 n 号城市。
输入：
数据保证没有任何两条高速公路的 x,y 是相同的。
数据保证所有城市都可以到 n 号城市。
每行两个整数 x,y(1≤x<y≤n) 描述一条从 x 号城市到 y 号城市的高速公路。
输出：
一行一个数表示蜗蜗期望经过多少条高速公路能够走到 n 号城市。由于答案是分数，请输出答案 mod 1e9+7。
对于期望：
定义：E(X) = Σxipi,即x的加权平均值
期望的性质：
1.E(ax+b) = aE(x)+b;
2.E(x+y) = E(x)+E(y);
3.E(xy) = E(x)E(y)
我们只要分别计算出经过1条，2条，...，n-1条高速公路走到n号城市的概率，就可以算出期望了
用f[i][j]表示经过j条高速公路走到i号城市的概率，有：
f[i][j] = Σ(x∈pre(i))f[x][j-1]/d[x]
最终答案等于：
Σ(i=1~n-1)f[n][i]*i
时间复杂度O(n*m log(p))
一次ksm代价log(p)
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1010;
const int p = 1e9+7;
int n,m;
std::vector<int>edge[N];
int f[N][N];
int ksm(int a,int b)
{
int ans = 1,base = a;
while(b)
{
if(b&1)
ans = (ans*base)%p;
base = (base*base)%p;
b>>=1;
}
return ans;
}
signed main()
{
cin>>n>>m;
for(int i = 1;i <= m; i++)
{
int x, y;
cin>>x>>y;
edge[x].push_back(y);
}
memset(f, 0, sizeof(f));
f[1][0] = 1;//经过0条路走到1号城市概率是1
for(int i = 1; i < n; i++)
{
int sz = edge[i].size();
for(int k = 0; k < n; k++)//枚举到目前为止走的k条路
if(f[i][k])
for(auto j : edge[i])//再枚举接下来去哪
{
f[j][k + 1] += f[i][k] * ksm(sz, p - 2);
f[j][k + 1] %= p;
}
}
int ans = 0;
for(int i = 1; i < n; i++)
{
ans += f[n][i] * i;
ans %= p;
}
cout<<ans<<endl;
return 0;
}
/*
能不能更快呢？
考虑从后往前算
用f[x]表示从x号城市出发期望经过多少条高速公路能够到达n号城市,f[n] = 0;
最后的f记录的是从x走到n经过的路的条数
在次考虑期望的定义 E(X) = Σxipi，
有f[x] = Σ(y∈nxt(x))(f[y]+1)/d[x] = Σ(y∈nxt(x))f[y]/d[x]+1
x走到y要走一条路,f[y]是y走到终点要走f[y]条路
x走到y,y再走到n
nxt(x)表示所有从x出发的高速公路的终点的集合
时间复杂度O(mlog(p))
▲！！！！！
记住求概率是从起点向终点求
要求的是期望从终点向起点求
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1010;
const int p = 1e9+7;
int n, m;
std::vector<int>edge[N];
int f[N];
int ksm(int a, int b)
{
int ans = 1, base = a;
while(b)
{
if(b & 1)
ans = (ans * base) % p;
base = (base * base) % p;
b >>= 1;
}
return ans;
}
signed main()
{
cin>>n>>m;
for(int i = 1; i <= m; i++)
{
int x, y;
cin>>x>>y;
edge[x].push_back(y);
}
memset(f, 0, sizeof(f));
f[n] = 0;
for(int i = n - 1; i; i--)
{
int sz = edge[i].size();
f[i] = 1;
for(auto j : edge[i])
{
f[i] += f[j] * ksm(sz, p - 2);
f[i] %= p;
}
}
cout<<f[1]<<endl;
return 0;
}
<div STYLE="page-break-after: always;"></div>
Backpack
Mixed backpack
//混合背包
/*
有n种物品和一个容量是m的背包。物品一共有三类
第一类01 si=-1
第二类完全 si=0
第三类多重 si>0
处理方法：
分类处理思想：
1.利用多重背包的二进制优化,可以先将多重背包转化为多个01背包
2.用a,b,c三个数组来记录转化之后所有背包的体积、价值、类型,c[i]==0表示完全背包,c[i]==1表示01背包
3.最后做一遍,以c的值分为两类，做完全背包和01背包
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int n, m, ty, v, w, s, a[N], b[N], c[N], f[N];
int main()
{
int num = 1;
cin>>n>>m;
for(int i = 1; i <= n; i++)
{
cin>>ty>>v>>w;
if(ty == 2){//完全背包
a[num] = v;
b[num] = w;
c[num++]=0;//背包类型
}
else
{
if(ty == 3)//多重
cin>>s;
else s = 1;
int k = 1;//k是拆分系数
while(s >= k)//二进制拆分
{
a[num] = k * v;
b[num] = k * w;
c[num++] = 1;//背包类型
s -= k;
k <<= 1;//k加倍
}
if(s)
{
a[num] = s * v;
b[num] = s * w;
c[num++] = 1;
}
}
}
//做一遍两类背包
for(int i = 1; i < num; i++)
{
if(c[i] == 1)//01
{
for(int j = m; j >= a[i]; j--)
{
f[j] = max(f[j], f[j - a[i]] + b[i]);
}
}
else{//完全
for(int j = a[i]; j <= m; j++)
{
f[j] = max(f[j], f[j - a[i]] + b[i]);
}
}
}
cout<<f[m]<<endl;
return 0;
}
/*
1.根据s的值分别处理三类背包,多吃背包可以用单调队列优化
2.可以把三类背包封装为三个函数
ZeroOnePack(int v,int w)
CompletePack(int v,int w)
MultiplePack(int v,int w,int s)
那么主函数
int v,w,s;
for(int i =1;i<=n;i++)
{
if(s==-1)
ZeroOnePack(v,w);
else if(s==0)
CompletePack(v,w)
else
MultiplePack(v,w,s)
}
*/
<div STYLE="page-break-after: always;"></div>
Partial backpack
#include<bits/stdc++.h>
using namespace std;
struct ty
{
double m, v;
}a[110];
double res[110];
bool cmp(ty a,ty b)
{
return a.v / a.m > b.v / b.m;
}
int main()
{
int n, t;
cin>>n>>t;
for(int i = 1; i <= n; i++) cin>>a[i].m>>a[i].v;
sort(a + 1, a + 1 + n, cmp);
double ans = 0;
for(int i = 1; i <= n; i++)
{
if(a[i].m <= t) ans += a[i].v, t -= a[i].m;
else
{
ans += a[i].v * t * (1.0) / (a[i].m * (1.0));
break;
}
}
printf("%.2f\n", ans);
return 0;
}
<div STYLE="page-break-after: always;"></div>
Pack pack
写法1
//分组背包
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n, V, f[N];
std::vector<pair<int,int>>a[N];
int main()
{
cin>>n>>V;
for(int i = 1; i <= n; i++)
{
int t;
cin>>t;
while(t--)
{
int v, w;
cin>>v>>w;
a[i].push_back({v, w});
}
}
for(int k = 1; k <= n; k++)
{
for(int i = V; i >= 0; i--)
{
for(auto x : a[k])
{
if(i >= x.first)
f[i] = max(f[i], f[i - x.first] + x.second);
}
}
}
cout<<f[V]<<endl;
return 0;
}
<div STYLE="page-break-after: always;"></div>
写法2
//n<=1000
#include<bits/stdc++.h>
using namespace std;
const int N = 1100;
int n, m, v[N], w[N], a[N], f[N];
std::vector<int> c[N];
int main()
{
cin>>n>>m;
for(int i = 1; i <= n; i++)
{
cin>>a[i]>>v[i]>>w[i];
c[a[i]].push_back(i);//记录编号
}
for(int i = 1; i <= 1000; i++)
{
for(int j = m; j >= 0; j--)//先枚举体积
{
for(auto k : c[i])//枚举第i组选的情况
{
if(v[k] <= j)
f[j] = max(f[j], f[j - v[k]] + w[k]);
}
}
}
cout<<f[m];
}
/*
5 10
1 1 6
1 6 9
1 5 6
2 4 5
2 5 10
16
*/