动态规划专题
A.Helping People
神仙概率题
容易发现给定的区间限制满足树形关系，考虑建树。
个人认为最难理解的一点是，期望最大值并不是简单相加，所以直接设期望DP是很难做的。
设 $ a[i] $ 表示原来第 \(i\) 个人的钱数， $ dp[i][j] $ 表示第 \(i\) 个节点最大钱数小于等于 $ max{ a_k (k在区间i的范围之内) }+j $ 的概率。注意这里用小于等于，方便DP，最后统计答案再查分一下就好。
下面我们用 $ m[i] $ 代表 \(i\) 区间原有钱数的最大值， $ p[i] $ 代表该区间的接受概率。
可以得到状态转移方程
\[dp_{u,i}= p[u]\times \Pi _{v \in son_u } dp_{v,i+m[u]-m[v]-1} +(1-p[u])\times \Pi _{v\in son_u}dp_{v,i+m[u]-m[v]} \]仔细理解一下这个方程，然后注意边界就好。复杂度 $ O(q^2) $
Code
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100,M=5e3+100;
struct vjudge{
int l,r,len,id,m;
double p;
}sug[M];
struct edge{
int to,next;
}e[M];
int n,q,a[N],cnt,head[M],depth[M],nleaf[M];
double dp[M][M],ans;
bool f[M];
bool cmp(vjudge a,vjudge b){
return a.len<b.len;
}
inline double Max(double x,double y){
if(x>y)return x;
else return y;
}
void add(int u,int v){
cnt++;
e[cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void dfs(int u,int fa){
dp[u][0]=1-sug[u].p;
depth[u]=depth[fa]+1;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
dfs(v,u);
}
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
dp[u][0]*=dp[v][sug[u].m-sug[v].m];
}
for(int i=1;i<=q;i++){
double x=1,y=1;
for(int j=head[u];j;j=e[j].next){
int v=e[j].to;
if(i+sug[u].m-sug[v].m>q)continue;
x*=dp[v][min(i+sug[u].m-sug[v].m-1,q)];
y*=dp[v][min(i+sug[u].m-sug[v].m,q)];
}
dp[u][i]=sug[u].p*x+(1-sug[u].p)*y;
}
}
int main()
{
scanf("%d%d",&n,&q);
int mm=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
mm=max(mm,a[i]);
}
for(int i=1;i<=q;i++){
scanf("%d%d%lf",&sug[i].l,&sug[i].r,&sug[i].p);
sug[i].len=sug[i].r-sug[i].l+1;
sug[i].id=i;
int maxn=0;
for(int j=sug[i].l;j<=sug[i].r;j++){
maxn=max(maxn,a[j]);
}
sug[i].m=maxn;
}
sort(sug+1,sug+q+1,cmp);
for(int i=1;i<=q;i++){
for(int j=i+1;j<=q;j++){
if(sug[i].l>=sug[j].l&&sug[i].r<=sug[j].r){
add(j,i);
nleaf[j]=1;
f[i]=1;
break;
}
}
}
++q;
sug[q]=(vjudge){1,n,n,q,mm,0};
for(int i=1;i<q;i++){
if(!f[i]){
add(q,i);
}
}
dfs(q,q);
for(int i=0;i<q;i++){
if(i==0)ans+=dp[q][i]*(i+sug[q].m);
else
ans+=(dp[q][i]-dp[q][i-1])*(i+sug[q].m);
}
printf("%0.9lf",ans);
}
B.Birds
简单背包
设 $ dp[i][j] $ 为走到第 \(i\) 棵树，抓了 \(j\) 只鸟剩余的最多魔法值。显然有：
\[dp[i][j]=\max \{dp[i-1][j-k]-cost[i]\times k+X \} \]注意两个边界。
-
$ dp[i-1][j-k]<0 $ 一定要跳过，不然可能产生错解。
-
$ dp[i-1][j-k]+X>W+b\times k $ 此时超出魔法上限。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3+10;
const int M=1e4+10;
int n,w,b,x,c[N],cost[N],dp[N][M];
int sum[N];
signed main()
{
scanf("%d%d%d%d",&n,&w,&b,&x);
for(int i=1;i<=n;i++){
scanf("%lld",&c[i]);
sum[i]=c[i]+sum[i-1];
}
for(int i=1;i<=n;i++){
scanf("%lld",&cost[i]);
}
memset(dp,128,sizeof(dp));
for(int i=0;i<=c[1];i++){
dp[1][i]=w-cost[1]*i;
}
for(int i=1;i<=n;i++){
for(int j=0;j<=c[i];j++){
for(int k=0;k<=sum[i-1];k++){
if(dp[i-1][k]<0)continue;
if(dp[i-1][k]+x>w+b*k)
dp[i][k+j]=max(dp[i][k+j],w+b*k-cost[i]*j);
else dp[i][k+j]=max(dp[i][k+j],dp[i-1][k]-cost[i]*j+x);
}
}
}
for(int i=1;i<=sum[n]+1;i++){
if(dp[n][i]<0){
printf("%lld\n",i-1);
return 0;
}
}
}
C.Positions in Permutations
我的做法可能看起来比较恶心，但本质上是一样的。
设 $ dp[i][j][x][y] $ 表示前 \(i\) 个数中选择 \(j\) 个作为好点，\(i-1\) 和 \(i\) 的状态，其中0代表不是好点，1代表选择前一个位置，2代表选择后一个位置，这样可以得到一坨方程。（见代码
$ sum[i][j] $ 表示前 \(i\) 个位置，有 \(j\) 个好点的方案数，将空白位置全排列，得到的是至少有 \(j\) 个好点的方案数。
在利用二项式反演求解。复杂度 $ O(n^2) $
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1100;
const int mod=1e9+7;
int n,p,dp[N][N][3][3];
int sum[N][N];
int jc[N],ny[N];
inline int C(int x,int y){
if(x<y)return 0;
return jc[x]*ny[y]%mod*ny[x-y]%mod;
}
signed main()
{
scanf("%lld%lld",&n,&p);
jc[0]=1;
for(int i=1;i<N;i++){
jc[i]=jc[i-1]*i%mod;
}
ny[0]=1;
ny[1]=1;
for(int i=2;i<N;i++){
ny[i]=(mod-mod/i)*ny[mod%i]%mod;
}
for(int i=2;i<N;i++){
ny[i]=ny[i-1]*ny[i]%mod;
}
sum[1][0]=dp[1][0][0][0]=1;
if(n!=1)
sum[1][1]=dp[1][1][0][2]=1;
for(int i=2;i<=n;i++){
sum[i][0]=dp[i][0][0][0]=1;
for(int j=1;j<=i;j++){
dp[i][j][0][0]=(dp[i-1][j][0][0]+dp[i-1][j][1][0]+dp[i-1][j][2][0])%mod;
dp[i][j][1][0]=(dp[i-1][j][0][1]+dp[i-1][j][1][1]+dp[i-1][j][2][1])%mod;
dp[i][j][2][0]=(dp[i-1][j][0][2]+dp[i-1][j][1][2]+dp[i-1][j][2][2])%mod;
dp[i][j][0][1]=(dp[i-1][j-1][0][0]+dp[i-1][j-1][1][0])%mod;
dp[i][j][1][1]=(dp[i-1][j-1][0][1]+dp[i-1][j-1][1][1])%mod;
dp[i][j][2][1]=(dp[i-1][j-1][0][2]+dp[i-1][j-1][1][2])%mod;
if(i!=n){
dp[i][j][0][2]=(dp[i-1][j-1][0][0]+dp[i-1][j-1][1][0]+dp[i-1][j-1][2][0])%mod;
dp[i][j][1][2]=(dp[i-1][j-1][0][1]+dp[i-1][j-1][1][1]+dp[i-1][j-1][2][1])%mod;
dp[i][j][2][2]=(dp[i-1][j-1][0][2]+dp[i-1][j-1][1][2]+dp[i-1][j-1][2][2])%mod;
}
sum[i][j]=(sum[i][j]+dp[i][j][1][1])%mod;
sum[i][j]=(sum[i][j]+dp[i][j][1][2])%mod;
sum[i][j]=(sum[i][j]+dp[i][j][2][1])%mod;
sum[i][j]=(sum[i][j]+dp[i][j][2][2])%mod;
if(i>=j+1){
sum[i][j]=(sum[i][j]+dp[i][j][0][1])%mod;
sum[i][j]=(sum[i][j]+dp[i][j][0][2])%mod;
sum[i][j]=(sum[i][j]+dp[i][j][1][0])%mod;
sum[i][j]=(sum[i][j]+dp[i][j][2][0])%mod;
if(i>=j+2)
sum[i][j]=(sum[i][j]+dp[i][j][0][0])%mod;
}
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<=i;j++){
sum[i][j]=(sum[i][j]*jc[i-j])%mod;
}
}
int ans=0;
for(int i=p,j=1;i<=n;i++,j=-j){
ans=(ans+j*sum[n][i]*C(i,p)%mod+mod)%mod;
}
cout<<ans<<endl;
}
H.Tavas in Kansas
题目背景让人感觉很纸张。
神奇博弈论
转换题面+一些技巧
-
我们最后想要的是两者得分的相对大小，由于两个人的得分不好同时维护，不妨将两人分数做差。
-
两人位置是不变的，跑最短路，距离离散化，将距离抽象成一个二维平面，以A的距离为横坐标，以B的距离为纵坐标，这样每个城市都映射到平面上。
-
$ dp[i][j][0/1] $ 表示当前状态下 A行动（0）或B行动（1），这样最后结果不好确定，所以考虑倒序DP。
通过以上操作，我们发现题目简单多了，每次A会按照坐标按行取数，B按列取数，但不能没取到。 $ O(n^2)DP $ 即可。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2200,M=2e5+100;
const int inf=2e9;
int n,m,s,t,p[N],cnt,head[M],ns,nt,dp[N][N][2];
int dis[2][N];
int vals[N],valt[N],ds[N],dt[N];
int num[N][N][2],siz[N][N][2];
struct edge{
int to,next,dis;
}e[M];
struct node{
int id,dis;
bool operator<(const node &x)const{
return dis>x.dis;
}
};
priority_queue<node>q;
struct froms{
int id,dis;
}diss[N];
struct fromt{
int id,dis;
}dist[N];
bool cmp3(froms x,froms y){
return x.dis<y.dis;
}
bool cmp4(fromt x,fromt y){
return x.dis<y.dis;
}
void add_edge(int u,int v,int c){
cnt++;
e[cnt].to=v;
e[cnt].next=head[u];
e[cnt].dis=c;
head[u]=cnt;
}
void dijkstra(int begin,int times){
dis[times][begin]=0;
q.push(node{begin,0});
while(!q.empty()){
node x=q.top();q.pop();
for(int i=head[x.id];i;i=e[i].next){
int y=e[i].to;
if(dis[times][y]>x.dis+e[i].dis){
dis[times][y]=x.dis+e[i].dis;
q.push(node{y,dis[times][y]});
}
}
}
}
signed main()
{
memset(dis,0x3f,sizeof(dis));
scanf("%lld%lld",&n,&m);
scanf("%lld%lld",&s,&t);
for(int i=1;i<=n;i++){
scanf("%lld",&p[i]);
}
int u,v,w;
for(int i=1;i<=m;i++){
scanf("%lld%lld%lld",&u,&v,&w);
add_edge(u,v,w);
add_edge(v,u,w);
}
dijkstra(s,0);
dijkstra(t,1);
for(int i=1;i<=n;i++){
diss[i]=froms{i,dis[0][i]};
dist[i]=fromt{i,dis[1][i]};
}
sort(diss+1,diss+n+1,cmp3);
sort(dist+1,dist+n+1,cmp4);
int tot=1;
vals[1]=p[diss[1].id];
ds[s]=1;
for(int i=2;i<=n;i++){
if(diss[i].dis==diss[i-1].dis){
vals[tot]+=p[diss[i].id];
ds[diss[i].id]=tot;
}
else{
tot++;
vals[tot]+=p[diss[i].id];
ds[diss[i].id]=tot;
}
}
ns=tot;
tot=1;
valt[1]=p[dist[1].id];
dt[t]=1;
for(int i=2;i<=n;i++){
if(dist[i].dis==dist[i-1].dis){
valt[tot]+=p[dist[i].id];
dt[dist[i].id]=tot;
}
else{
tot++;
valt[tot]+=p[dist[i].id];
dt[dist[i].id]=tot;
}
}
nt=tot;
for(int i=1;i<=n;i++){
num[ds[i]][dt[i]][0]+=p[i];
num[ds[i]][dt[i]][1]+=p[i];
siz[ds[i]][dt[i]][0]++;
siz[ds[i]][dt[i]][1]++;
}
for(int i=0;i<=ns;i++){
for(int j=nt;j>=0;j--){
num[i][j][0]+=num[i][j+1][0];
siz[i][j][0]+=siz[i][j+1][0];
}
}
for(int i=0;i<=nt;i++){
for(int j=ns;j>=0;j--){
num[j][i][1]+=num[j+1][i][1];
siz[j][i][1]+=siz[j+1][i][1];
}
}
for(int i=ns;i>=0;i--){
for(int j=nt;j>=0;j--){
if(i==ns&&j==nt)continue;
if(i!=ns){
if(siz[i+1][j+1][0]){
dp[i][j][0]=max(dp[i+1][j][0],dp[i+1][j][1])+num[i+1][j+1][0];
}
else dp[i][j][0]=dp[i+1][j][0];
}
if(j!=nt){
if(siz[i+1][j+1][1]){
dp[i][j][1]=min(dp[i][j+1][0],dp[i][j+1][1])-num[i+1][j+1][1];
}
else dp[i][j][1]=dp[i][j+1][1];
}
}
}
if(dp[0][0][0]==0)puts("Flowers");
if(dp[0][0][0]>0)puts("Break a heart");
if(dp[0][0][0]<0)puts("Cry");
}