AtCoder dp 26题
A - Frog 1
题目已然给出了转移方程，设 \(dp_i\) 为到第 \(i\) 块石头的最小代价。
转移方程：
时间复杂度：\(O(n)\)
点击查看代码
int n;
int h[maxn],dp[maxn];
int main(){
n=read();
for(int i=1;i<=n;++i) h[i]=read();
dp[1]=0,dp[2]=abs(h[1]-h[2]);
for(int i=3;i<=n;++i){
dp[i]=min(dp[i-2]+abs(h[i-2]-h[i]),dp[i-1]+abs(h[i-1]-h[i]));
}
print
B - Frog 2
多了一层步数的限制，枚举一下即可，\(dp_i\) 定义同上。
转移方程：
时间复杂度：\(O(nK)\)
点击查看代码
int n,k;
int h[maxn],dp[maxn];
int main(){
n=read(),k=read();
for(int i=1;i<=n;++i) h[i]=read(),dp[i]=maxxn;
dp[1]=0;
for(int i=1;i<=n;++i){
for(int j=i+1;j<=min(i+k,n);++j){
dp[j]=min(dp[j],dp[i]+abs(h[i]-h[j]));
}
}
printf("%d\n",dp[n]);
return 0;
}
C - Vacation
相当朴素，设 \(dp_{i,0/1/2}\) 分别表示第 \(i\) 天进行某种活动的最大收益，从第 \(i-1\) 天的两个不同状态转移即可。
时间复杂度：\(O(n)\)
点击查看代码
int n;
int a[maxn],b[maxn],c[maxn];
int dp[maxn][3];
int main(){
n=read();
for(int i=1;i<=n;++i) a[i]=read(),b[i]=read(),c[i]=read();
dp[1][0]=a[1],dp[1][1]=b[1],dp[1][2]=c[1];
for(int i=2;i<=n;++i){
dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i];
dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i];
dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c[i];
}
printf("%d\n",max({dp[n][0],dp[n][1],dp[n][2]}));
return 0;
}
D - Knapsack 1
传统背包问题，设 \(dp_i\) 为已然使用重量 \(i\) 时的最大价值，正序枚举每个物品再倒序枚举重量即可。（完全滚掉一维，不能产生冲突）
转移方程：
时间复杂度：\(O(nW)\)
点击查看代码
int n,m;
int w[maxn];
ll v[maxn];
ll dp[maxn];
ll ans;
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i) w[i]=read(),v[i]=read();
for(int i=1;i<=n;++i){
for(int j=m;j>=w[i];--j){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
for(int i=0;i<=m;++i) ans=max(ans,dp[i]);
printf("%lld\n",ans);
return 0;
}
E - Knapsack 2
略微有所改动，这里的代价扩大到 \(10^9\) 级别，而总价值缩小了，因此可以仿照上一题，将状态改为 \(dp_i\) 表示得到价值为 \(i\) 的物品的最小代价，同上一题枚举即可。答案为倒序第一个最小代价合法的价值。
转移方程：
时间复杂度：\(O(n\sum v)\)
点击查看代码
int n,m;
int w[105],v[105],sum;
int dp[maxn];
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i) w[i]=read(),v[i]=read(),sum+=v[i];
memset(dp,0x3f,sizeof(dp));
dp[0]=0,dp[v[1]]=w[1];
for(int i=2;i<=n;++i){
for(int j=sum;j>=v[i];--j){
if(dp[j-v[i]]+w[i]>m) continue;
dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
}
}
for(int i=sum;i>=0;--i){
if(dp[i]<=m) return printf("%d\n",i),0;
}
return 0;
}
F - LCS
设 \(dp_{i,j}\) 为 \(s\) 前 \(i\) 位与 \(t\) 前 \(j\) 位的最大公共子串。
转移方程：
当 \(s_i=t_j\) 时，还存在转移方程：
\[dp_{i,j}=\max(dp_{i,j},dp_{i-1,j-1}+1) \]时间复杂度：\(O(|s||t|)\)
输出路径另开数组记录一下，老生常谈了。
点击查看代码
int ls,lt;
char s[3005],t[3005];
int dp[3005][3005],pre[3005][3005][2],mark[3005][3005];
void print(int x,int y){
if(!x||!y) return;
print(pre[x][y][0],pre[x][y][1]);
if(mark[x][y]) printf("%c",s[x]);
}
int main(){
scanf("%s",s+1);
scanf("%s",t+1);
ls=strlen(s+1),lt=strlen(t+1);
for(int i=1;i<=ls;++i){
for(int j=1;j<=lt;++j){
if(s[i]==t[j]&&dp[i-1][j-1]+1>dp[i][j]){
dp[i][j]=dp[i-1][j-1]+1;
pre[i][j][0]=i-1,pre[i][j][1]=j-1;
mark[i][j]=1;
}
if(dp[i-1][j]>dp[i][j]){
dp[i][j]=dp[i-1][j];
pre[i][j][0]=i-1,pre[i][j][1]=j;
mark[i][j]=0;
}
if(dp[i][j-1]>dp[i][j]){
dp[i][j]=dp[i][j-1];
pre[i][j][0]=i,pre[i][j][1]=j-1;
mark[i][j]=0;
}
}
}
print(ls,lt);
printf("\n");
return 0;
}
G - Longest Path
DAG 上的 dp，用拓扑排序来转移成线性问题，在队首出队并删去对节点的入度贡献时，可以同时更新答案。
转移方程：
时间复杂度：\(O(m)\)
点击查看代码
int n,m;
vector<int> E[maxn];
queue<int> q;
int deg[maxn];
int dp[maxn];
int ans;
int main(){
n=read(),m=read();
for(int i=1;i<=m;++i){
int u=read(),v=read();
E[u].push_back(v);
++deg[v];
}
for(int i=1;i<=n;++i){
if(!deg[i]) q.push(i);
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int v:E[u]){
dp[v]=max(dp[v],dp[u]+1);
--deg[v];
if(!deg[v]) q.push(v);
}
}
for(int i=1;i<=n;++i){
ans=max(ans,dp[i]);
}
printf("%d\n",ans);
return 0;
}
H - Grid 1
坐标 dp，也比较简单，设 \(dp_{i,j}\) 表示 \((1,1)\) 到 \((i,j)\) 的路径数目，对于每一个标记为 . 的坐标，从上方和左侧两个位置的状态转移即可。
转移方程：
时间复杂度：\(O(HW)\)
点击查看代码
int n,m;
char s[1005][1005];
int dp[1005][1005];
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i) scanf("%s",s[i]+1);
dp[1][1]=1;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(i==1&&j==1) continue;
if(s[i][j]=='.') dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
}
}
printf("%d\n",dp[n][m]);
return 0;
}
I - Coins
直接转移的概率 dp，设 \(dp_{i,j}\) 表示前 \(i\) 枚硬币，有 \(j\) 枚正面向上的概率。
转移方程：
时间复杂度：\(O(n^2)\)
点击查看代码
int n;
db p[3005];
db dp[3005][3005];
db ans;
int main(){
n=read();
for(int i=1;i<=n;++i) scanf("%Lf",&p[i]);
dp[1][0]=1.0-p[1],dp[1][1]=p[1];
for(int i=2;i<=n;++i){
for(int j=0;j<=i;++j){
if(!j) dp[i][j]=dp[i-1][j]*(1.0-p[i]);
else if(i==j) dp[i][j]=dp[i-1][j-1]*p[i];
else dp[i][j]=dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i]);
}
}
for(int i=(n+1)/2;i<=n;++i) ans+=dp[n][i];
printf("%.11Lf\n",ans);
return 0;
}
J - Sushi
带自环的期望 dp，多数要倒推+移项。
考虑 \(a\) 的值只有三种，将其列入状态中，即 \(dp(i,j,k)\) 表示还有 \(i\) 个盘子剩 \(1\) 个,\(j\) 个盘子剩 \(2\) 个，\(k\) 个盘子剩 \(3\) 个的期望步数。
转移方程：
化简一下得到：
\[dp(i,j,k)=\dfrac{n}{i+j+k}+\dfrac{i}{i+j+k}\times dp(i-1,j,k)+\dfrac{j}{i+j+k}\times dp(i+1,j-1,k)+\dfrac{k}{i+j+k}\times dp(i,j+1,k-1) \]考虑到只有 \(k\) 有单调性，可以对 \(k\) 枚举，也可以记忆化搜索。
时间复杂度：\(O(n^3)\)
点击查看代码
int n;
int a[305],tot[4];
db dp[305][305][305];
db ans;
db dfs(int i,int j,int k){
if(!i&&!j&&!k) return 0.0;
if(dp[i][j][k]!=0) return dp[i][j][k];
dp[i][j][k]=1.0*n/(i+j+k);
if(i) dp[i][j][k]+=1.0*i/(i+j+k)*dfs(i-1,j,k);
if(j) dp[i][j][k]+=1.0*j/(i+j+k)*dfs(i+1,j-1,k);
if(k) dp[i][j][k]+=1.0*k/(i+j+k)*dfs(i,j+1,k-1);
return dp[i][j][k];
}
int main(){
n=read();
for(int i=1;i<=n;++i){
a[i]=read();
++tot[a[i]];
}
ans=dfs(tot[1],tot[2],tot[3]);
printf("%.12LF\n",ans);
return 0;
}
K - Stones
感觉是博弈论，但是集合大小和值域大小都可以枚举，设 \(dp_{i,0/1}\) 表示 \(i\) 个石子时，先手或后手是否必胜，这一次操作先手必胜和上一次操作的后手必胜是或运算关系。
时间复杂度：\(O(nK)\)
点击查看代码
int n,m;
int a[105];
int dp[maxn][2];
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i){
a[i]=read();
dp[a[i]][0]=1;
}
for(int i=1;i<=m;++i){
for(int j=1;j<=n&&a[j]<=i;++j){
dp[i][0]|=dp[i-a[j]][1];
}
dp[i][1]=dp[i][0]^1;
}
if(dp[m][0]) printf("First\n");
else printf("Second\n");
return 0;
}
L - Deque
首先要分先后手来进行 \(\max\) 或 \(\min\) 的转移，开始想了个 \(dp_{i,j}\) 表示队首取了 \(i\) 个，队尾取了 \(j\) 个的最优答案，发现假了，原因是这种正序递推无法保证上一次最优的情况就是可以实现的（先后手均采用最优决策）。
因此考虑倒推，设 \(dp_{l,r}\) 为剩余队列中 \([l,r]\) 的元素的最佳答案，这样可以讨论先后手。
已选取的个数为偶数（先手）转移方程：
已选取的个数为奇数（后手）转移方程：
\[dp_{l,r}=\min(dp_{l+1,r}-a_l,dp_{l,r-1}-a_r) \]时间复杂度：\(O(n^2)\)
点击查看代码
int n;
ll a[3005];
ll dp[3005][3005];
int main(){
n=read();
for(int i=1;i<=n;++i) a[i]=read();
for(int k=1;k<=n;++k){
for(int l=1,r=k;r<=n;++l,++r){
if((n-k)&1) dp[l][r]=min(dp[l+1][r]-a[l],dp[l][r-1]-a[r]);
else dp[l][r]=max(dp[l+1][r]+a[l],dp[l][r-1]+a[r]);
}
}
printf("%lld\n",dp[1][n]);
return 0;
}
M - Candies
设 \(dp_{i,j}\) 表示前 \(i\) 个位置放累计 \(j\) 个糖的方案数。
转移方程：
明显的前缀和优化，需要判一下边界，再就是前缀和要算到最大，即 \(K\)。
时间复杂度：\(O(nK)\)
点击查看代码
int n,m;
int a[105],sum[105];
int dp[105][maxn],sumdp[maxn];
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i) a[i]=read(),sum[i]=sum[i-1]+a[i];
for(int i=0;i<=a[1];++i) dp[1][i]=1,sumdp[i]=i+1;
for(int i=a[1]+1;i<=m;++i) sumdp[i]=a[1]+1;
for(int i=2;i<=n;++i){
dp[i][0]=1;
for(int j=1;j<=min(m,sum[i]);++j){
if(j-a[i]>0) dp[i][j]=(sumdp[j]-sumdp[j-a[i]-1]+mod)%mod;
else dp[i][j]=sumdp[j];
}
sumdp[0]=dp[i][0];
for(int j=1;j<=m;++j){
sumdp[j]=(sumdp[j-1]+dp[i][j])%mod;
}
}
printf("%d\n",dp[n][m]);
return 0;
}
N - Slimes
区间 dp，设 \(dp_{l,r}\) 为区间 \([l,r]\) 内的最大答案，求一个前缀和，枚举断点即可。
转移方程：
时间复杂度：\(O(n^3)\)
点击查看代码
int n;
ll a[405],sum[405];
ll dp[405][405];
int main(){
n=read();
for(int i=1;i<=n;++i) a[i]=read(),sum[i]=sum[i-1]+a[i];
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=n;++i) dp[i][i]=0;
for(int k=2;k<=n;++k){
for(int l=1,r=k;r<=n;++l,++r){
for(int i=l;i<r;++i){
dp[l][r]=min(dp[l][r],dp[l][i]+dp[i+1][r]+sum[r]-sum[l-1]);
}
}
}
printf("%lld\n",dp[1][n]);
return 0;
}
O - Matching
看数据范围知状压，设 \(dp_{i,s}\) 表示前 \(i\) 个左侧点匹配右侧点状态为 \(s\) 的方案数。不难发现，转移的条件是 \(\operatorname{popcount}(s)=i\)，可以优化。
时间复杂度：\(O(n2^n)\)
点击查看代码
int n;
int st[23];
int dp[23][maxn];
int stcnt[maxn];
vector<int> S[23];
int main(){
n=read();
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
int x=read();
if(x) st[i]|=(1<<(j-1));
}
}
for(int i=1;i<=n;++i) stcnt[1<<(i-1)]=1;
for(int i=0;i<(1<<n);++i){
int k=i&-i;
if(k&&!stcnt[i]) stcnt[i]=stcnt[i^k]+1;
S[stcnt[i]].push_back(i);
}
for(int i=1;i<=n;++i){
if(st[1]&(1<<(i-1))) dp[1][(1<<(i-1))]=1;
}
for(int i=2;i<=n;++i){
for(int s:S[i-1]){
for(int j=1;j<=n;++j){
if(s&(1<<(j-1))) continue;
if(!(st[i]&(1<<(j-1)))) continue;
dp[i][s|(1<<(j-1))]=(dp[i][s|(1<<(j-1))]+dp[i-1][s])%mod;
}
}
}
printf("%d\n",dp[n][(1<<n)-1]);
return 0;
}
P - Independent Set
树形 dp，设 \(dp_{u,0/1}\) 表示 \(u\) 号节点子树内在 \(u\) 染黑或染白的情况下的方案数。注意这里求方案数而非最大答案，是乘法原理。
转移方程：
时间复杂度：\(O(n)\)
点击查看代码
Q - Flowers
朴素做法是设 \(dp_i\) 表示把 \(i\) 作为最后一个元素的最大权值和。
转移方程：
发现是在 \(p\) 上的连续区间中取 \(\max\)，可以用线段树优化。
时间复杂度：\(O(n\log n)\)
点击查看代码
int n;
int h[maxn];
ll a[maxn];
struct SegmentTree{
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
ll mx[maxn<<2];
void update(int rt,int l,int r,int p,ll k){
if(l==r){
mx[rt]=k;
return;
}
if(p<=mid) update(lson,p,k);
else update(rson,p,k);
mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
}
ll query(int rt,int l,int r,int pl,int pr){
if(pl<=l&&r<=pr) return mx[rt];
ll res=0;
if(pl<=mid) res=max(res,query(lson,pl,pr));
if(pr>mid) res=max(res,query(rson,pl,pr));
return res;
}
#undef mid
#undef lson
#undef rson
}S;
ll ans;
int main(){
n=read();
for(int i=1;i<=n;++i) h[i]=read();
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<=n;++i){
if(h[i]==1){
ans=max(ans,a[i]);
S.update(1,1,n,h[i],a[i]);
}
else{
ll now=S.query(1,1,n,1,h[i]-1)+a[i];
ans=max(ans,now);
S.update(1,1,n,h[i],now);
}
}
printf("%lld\n",ans);
return 0;
}
R - Walk
邻接矩阵可以模拟 Floyd 做法，根据矩阵乘法的结合律，使用快速幂优化。
时间复杂度：\(O(n^3\log K)\)
点击查看代码
int n;
ll m;
struct Matrix{
int num[55][55];
Matrix(){
memset(num,0,sizeof(num));
}
Matrix operator*(const Matrix&rhs)const{
Matrix res;
for(int i=1;i<=n;++i){
for(int k=1;k<=n;++k){
for(int j=1;j<=n;++j){
res.num[i][j]=(res.num[i][j]+1ll*num[i][k]*rhs.num[k][j]%mod)%mod;
}
}
}
return res;
}
}a;
inline Matrix q_pow(Matrix x,ll p){
Matrix res=x;
--p;
while(p){
if(p&1) res=res*x;
x=x*x;
p>>=1;
}
return res;
}
int ans;
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
a.num[i][j]=read();
}
}
a=q_pow(a,m);
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
ans=(ans+a.num[i][j])%mod;
}
}
printf("%d\n",ans);
return 0;
}
S - Digit Sum
数位 dp，使用记忆化搜索，设 \(dp_{i,0/1,j}\) 表示前 \(i\) 位有无最大值限制且加和模 \(D\) 为 \(j\) 的方案数。
需要去掉 \(0\) 的情况。
时间复杂度：\(O(D\lg K)\)
点击查看代码
int n,d;
char s[maxn];
int a[maxn];
int dp[maxn][2][105];
int dfs(int x,bool lim,int num){
if(x==n+1){
if(!num) return 1;
else return 0;
}
if(dp[x][lim][num]!=-1) return dp[x][lim][num];
int res=0,mx=9;
if(lim) mx=a[x];
for(int i=0;i<=mx;++i){
if(lim&&i==a[x]) res=(res+dfs(x+1,1,(num+i)%d))%mod;
else res=(res+dfs(x+1,0,(num+i)%d))%mod;
}
return dp[x][lim][num]=res;
}
int ans;
int main(){
scanf("%s",s+1);
n=strlen(s+1);
d=read();
for(int i=1;i<=n;++i){
a[i]=s[i]-'0';
}
memset(dp,-1,sizeof(dp));
ans=(dfs(1,1,0)-1+mod)%mod;
printf("%d\n",ans);
return 0;
}
T - Permutation
排列计数 dp，发现如果将填入的数字设为状态会有不合法状态，考虑用排名作为状态。设 \(dp_{i,j}\) 表示前 \(i\) 个数中，第 \(i\) 个数从小到大排名为 \(j\) 的方案数。
对于 < 的情况，第 \(i-1\) 的排名低于 \(i\)，所以转移方程：
对于 > 的情况，第 \(i-1\) 的排名不低于 \(i\)，注意加入 \(i\) 后 \(i-1\) 的排名会上升一位，所以转移方程：
可以前缀和优化。
时间复杂度：\(O(n^2)\)
点击查看代码
int n;
char s[3005];
int dp[3005][3005];
int sum[3005];
int main(){
n=read();
scanf("%s",s+2);
dp[1][1]=1;
for(int i=1;i<=n;++i) sum[i]=1;
for(int i=2;i<=n;++i){
for(int j=1;j<=i;++j){
if(j==1&&s[i]=='<') continue;
if(j==i&&s[i]=='>') continue;
if(s[i]=='<'){
dp[i][j]=(dp[i][j]+sum[j-1])%mod;
}
else{
dp[i][j]=(dp[i][j]+sum[i-1]-sum[j-1]+mod)%mod;
}
}
for(int j=1;j<=n;++j) sum[j]=(sum[j-1]+dp[i][j])%mod;
}
printf("%d\n",sum[n]);
return 0;
}
U - Grouping
先预处理出每个选取状态的贡献和 \(sum\)，设 \(dp_=S\) 为状态为 \(S\) 的最大贡献，枚举子集。
转移方程：
时间复杂度：\(O(n^22^n+3^n)\)
点击查看代码
int n;
ll a[20][20];
ll st[maxn];
ll dp[maxn];
int main(){
n=read();
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
a[i][j]=read();
}
}
for(int s=0;s<(1<<n);++s){
for(int i=1;i<=n;++i){
if(!(s&(1<<(i-1)))) continue;
for(int j=i+1;j<=n;++j){
if(!(s&(1<<(j-1)))) continue;
st[s]+=a[i][j];
}
}
}
for(int s=0;s<(1<<n);++s){
for(int s1=s;s1;s1=s&(s1-1)){
int s2=s^s1;
dp[s]=max(dp[s],st[s1]+dp[s2]);
}
}
printf("%lld\n",dp[(1<<n)-1]);
return 0;
}
V - Subtree
换根 dp，先考虑根节点为 \(1\) 如何计算，设 \(dp_{u}\) 为该节点染成黑色的方案数。
转移方程：
考虑换根，发现答案 \(ans_u\) 的来源分三部分：\(u\) 子树内的方案数，\(u\) 父亲 \(f\) 除 \(u\) 子树之外的方案数以及 \(u\) 祖先除 \(u\) 所在子树的方案数。
第一部分即为 \(dp_u\)，第二部分即为：\(\dfrac{dp_f}{dp_u+1}\)，第三部分实际上来自上一层第二部分。
现在问题在于模数不保证为质数，可能存在逆元，解决方法为维护前缀积和后缀积，直接算没有 \(dp_u+1\) 时 \(dp_f\) 的值。
时间复杂度：\(O(n)\)
点击查看代码
int n,mod;
vector<int> E[maxn],son[maxn],pre[maxn],suf[maxn];
int dp[maxn],ans[maxn];
void dfs(int u,int f){
dp[u]=1;
for(int i=0;i<E[u].size();++i){
int v=E[u][i];
if(v==f) continue;
son[u].push_back(v);
dfs(v,u);
dp[u]=1ll*dp[u]*(dp[v]+1)%mod;
}
int now=1;
for(int i=0;i<son[u].size();++i){
int v=son[u][i];
now=1ll*now*(dp[v]+1)%mod;
pre[u].push_back(now);
}
now=1;
for(int i=son[u].size()-1;i>=0;--i){
int v=son[u][i];
now=1ll*now*(dp[v]+1)%mod;
suf[u].push_back(now);
}
reverse(suf[u].begin(),suf[u].end());
}
void secdfs(int u,int prod){
ans[u]=1ll*dp[u]*(prod+1)%mod;
for(int i=0;i<son[u].size();++i){
int v=son[u][i],tmp=prod+1;
if(i) tmp=1ll*tmp*pre[u][i-1]%mod;
if(i!=son[u].size()-1) tmp=1ll*tmp*suf[u][i+1]%mod;
secdfs(v,tmp);
}
}
int main(){
n=read(),mod=read();
for(int i=1;i<n;++i){
int u=read(),v=read();
E[u].push_back(v);
E[v].push_back(u);
}
dfs(1,0);
secdfs(1,0);
for(int i=1;i<=n;++i) printf("%d\n",ans[i]);
return 0;
}
W - Intervals
据说是套路题，套路貌似在于为保证不重不漏，枚举右端点记录答案。
于是设 \(dp_{i,j}\) 表示在前 \(i\) 个位置中，上一个 \(1\) 在 \(j\) 的最大贡献，注意这里只包含右端点在 \([1,i]\) 的贡献。
转移方程：
特别地，对于 \(dp_{i,i}\) 有：
\[dp_{i,i}=\max(\max_{j=1}^{i-1}\{dp_{i-1,j}\},0) \]这样枚举状态和区间修改的复杂度都是 \(O(n^2)\) 的，使用线段树优化，可以规避掉对第二维的枚举。
时间复杂度：\(O(n\log n)\)
点击查看代码
int n,m;
struct node{
int l,r;
ll w;
node()=default;
node(int l_,int r_,ll w_):l(l_),r(r_),w(w_){}
}a[maxn];
vector<node> gr[maxn];
struct SegmentTree{
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
ll mx[maxn<<2],tag[maxn<<2];
void build(int rt,int l,int r){
mx[rt]=0,tag[rt]=0;
if(l==r) return;
build(lson),build(rson);
}
void push_down(int rt){
if(tag[rt]){
tag[rt<<1]+=tag[rt],tag[rt<<1|1]+=tag[rt];
mx[rt<<1]+=tag[rt],mx[rt<<1|1]+=tag[rt];
tag[rt]=0;
}
}
void update(int rt,int l,int r,int pl,int pr,ll k){
if(pl<=l&&r<=pr){
mx[rt]+=k,tag[rt]+=k;
return;
}
push_down(rt);
if(pl<=mid) update(lson,pl,pr,k);
if(pr>mid) update(rson,pl,pr,k);
mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
}
#undef mid
#undef lson
#undef rson
}S;
int main(){
n=read(),m=read();
for(int i=1;i<=m;++i){
int l=read(),r=read(),w=read();
a[i]=node(l,r,w);
gr[r].push_back(a[i]);
}
S.build(1,1,n);
for(int r=1;r<=n;++r){
S.update(1,1,n,r,r,max(S.mx[1],0ll));
for(int j=0;j<gr[r].size();++j){
int l=gr[r][j].l;
ll w=gr[r][j].w;
S.update(1,1,n,l,r,w);
}
}
printf("%lld\n",max(S.mx[1],0ll));
return 0;
}
X - Tower
比较厉害的题。
需要找到一种方式排序（不需要考虑价值），之后转换成背包问题。
貌似也是一个经典思路，考虑排序的关键字其实等价于冒泡排序中是否要交换。那么前面已经堆叠的塔重量为 \(W\)，则 \(i\) 应当处于 \(j\) 之前当且仅当：
也就是：
\[s_i+w_i<s_j+w_j \]之后就是背包问题，只不过代价的上界是变化的。
时间复杂度：\(O(n(W+S))\)
点击查看代码
int n;
struct node{
int w,s;
ll v;
bool operator<(const node&rhs)const{
return w+s<rhs.w+rhs.s;
}
}a[1005];
ll dp[20005];
ll ans;
int main(){
n=read();
for(int i=1;i<=n;++i){
a[i].w=read(),a[i].s=read(),a[i].v=read();
}
sort(a+1,a+n+1);
for(int i=1;i<=n;++i){
for(int j=min(a[i].s+a[i].w,20000);j>=a[i].w;--j){
dp[j]=max(dp[j],dp[j-a[i].w]+a[i].v);
}
}
for(int i=0;i<=20000;++i){
ans=max(ans,dp[i]);
}
printf("%lld\n",ans);
return 0;
}
Y - Grid 2
计数 dp，不需要高难度容斥。
经典的计算路径方法，是从 \((x_1,y_1)\) 到 \((x_2,y_2)\)，方案数为 \(\dbinom{x_2-x_1+y_2-y_1}{x_2-x_1}\)，我们需要去掉经过障碍的方案数。
发现障碍和终点计算时的要求是一致的——之前不能经过其他障碍，于是设 \(dp_i\) 表示到第 \(i\) 个障碍且不经过其他障碍的方案数，若把终点视作第 \(n+1\) 个障碍，并将障碍递增排序，即可保证在之前可能会经过的障碍的 \(dp\) 值已然被计算。
转移方程：
时间复杂度：\(O(n^2)\)
点击查看代码
int h,w,n;
struct node{
int x,y;
bool operator<(const node&rhs)const{
if(x==rhs.x) return y<rhs.y;
return x<rhs.x;
}
}a[3005];
int dp[3005];
int fac[maxn],finv[maxn];
inline int q_pow(int x,int p){
int res=1;
while(p){
if(p&1) res=1ll*res*x%mod;
x=1ll*x*x%mod;
p>>=1;
}
return res;
}
inline int C(int N,int M){
return 1ll*fac[N]*finv[M]%mod*finv[N-M]%mod;
}
int main(){
h=read(),w=read(),n=read();
fac[0]=finv[0]=1;
for(int i=1;i<=h+w;++i) fac[i]=1ll*fac[i-1]*i%mod;
finv[h+w]=q_pow(fac[h+w],mod-2);
for(int i=h+w-1;i>=1;--i) finv[i]=1ll*finv[i+1]*(i+1)%mod;
for(int i=1;i<=n;++i){
a[i].x=read(),a[i].y=read();
}
sort(a+1,a+n+1);
a[++n].x=h,a[n].y=w;
for(int i=1;i<=n;++i){
dp[i]=C(a[i].x+a[i].y-2,a[i].x-1);
for(int j=1;j<i;++j){
if(a[j].x<=a[i].x&&a[j].y<=a[i].y){
dp[i]=(dp[i]-1ll*dp[j]*C(a[i].x+a[i].y-a[j].x-a[j].y,a[i].x-a[j].x)%mod+mod)%mod;
}
}
}
printf("%d\n",dp[n]);
return 0;
}
Z - Frog 3
非常板的斜率优化。
设 \(dp_i\) 为到第 \(i\) 块石头的最小代价，直接来看转移方程：
我们把最小值去掉：
\[dp_i=dp_j+(h_i-h_j)^2+C \]\[dp_i=dp_j+h_i^2-2\times h_i\times h_j+h_j^2+C \]移项得到：
\[dp_i-h_i^2-C=dp_j+h_j^2-2\times h_i\times h_j \]即得到了形如 \(b=y-kx\) 的形式。
其中：
求最小值，即单调队列维护一个下凸壳。
时间复杂度：\(O(n)\)
点击查看代码
int n;
ll C,h[maxn];
ll dp[maxn];
inline db X(int i){
return 1.0*h[i];
}
inline db Y(int i){
return 1.0*(dp[i]+h[i]*h[i]);
}
inline db slope(int i,int j){
return (Y(j)-Y(i))/(X(j)-X(i));
}
int q[maxn],head,tail;
int main(){
n=read(),C=read();
for(int i=1;i<=n;++i) h[i]=read();
dp[1]=0;
head=1,tail=0;
q[++tail]=1;
for(int i=2;i<=n;++i){
while(head<tail&&slope(q[head],q[head+1])<=2.0*h[i]) ++head;
dp[i]=dp[q[head]]+(h[i]-h[q[head]])*(h[i]-h[q[head]])+C;
while(head<tail&&slope(q[tail],i)<=slope(q[tail-1],q[tail])) --tail;
q[++tail]=i;
}
printf("%lld\n",dp[n]);
return 0;
}