期望dp
P1850
设\(f[i][j][0/1]\)表示考虑到第\(i\)个教室，用了\(j\)次交换权并且\(i\)换与不换的最小值。
每次的新贡献只用考虑\(i\)与\(i-1\)之间的最短路以及他们成功的概率.
#include<iostream>
#include<cstdio>
#include<cstring>
#define db double
using namespace std;
const int N=2200,V=330;
const double INF=1e18;
int dis[N][N];
int n,m,v,e,a,b,w;
db f[N][N][2];
struct room{
int c,d;db k;
}s[N];
void floyd(){
for(int i=1;i<=v;++i)dis[i][i]=0;
for(int k=1;k<=v;++k)
for(int i=1;i<=v;++i)
for(int j=1;j<=v;++j){
if(i==j)continue;
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
void init(){
memset(dis,0x3f,sizeof dis);
for(int i=0;i<=n+1;++i)
for(int j=0;j<=m+1;++j)
f[i][j][0]=f[i][j][1]=INF;
}
inline db Min(db a,db b){return a<b?a:b;}
int main(){
scanf("%d%d%d%d",&n,&m,&v,&e);
for(int i=1;i<=n;++i)scanf("%d",&s[i].c);
for(int i=1;i<=n;++i)scanf("%d",&s[i].d);
for(int i=1;i<=n;++i)scanf("%lf",&s[i].k);
init();
for(int i=1;i<=e;++i){
scanf("%d%d%d",&a,&b,&w);
dis[a][b]=min(dis[a][b],w);
dis[b][a]=min(dis[b][a],w);
}
floyd();
f[1][0][0]=0.0;f[1][1][1]=0.0;
for(int i=2;i<=n;++i){
for(int j=0;j<=m;++j){
db kv=s[i-1].k,ku=s[i].k;
int uc=s[i].c,ud=s[i].d,vc=s[i-1].c,vd=s[i-1].d;
f[i][j][0]=Min(f[i][j][0],f[i-1][j][0]+1.0*1.0*(double)dis[vc][uc]);
f[i][j][0]=Min(f[i][j][0],f[i-1][j][1]+kv*(double)dis[vd][uc]+(1.0-kv)*(double)dis[vc][uc]);
if(j==0)continue;
f[i][j][1]=Min(f[i][j][1],f[i-1][j-1][0]+ku*(double)dis[vc][ud]+(1.0-ku)*(double)dis[vc][uc]);
f[i][j][1]=Min(f[i][j][1],f[i-1][j-1][1]+
ku*kv*(double)dis[vd][ud]+
kv*(1.0-ku)*(double)dis[vd][uc]+
ku*(1.0-kv)*(double)dis[vc][ud]+
(1.0-ku)*(1.0-kv)*(double)dis[vc][uc]);
}
}
db ans=INF;
for(int i=0;i<=m;++i)ans=Min(ans,Min(f[n][i][0],f[n][i][1]));
printf("%.2lf",ans);
return 0;
}
计数dp
字符串类计数
P2679
f[i][j][k][0/1]表示a串前i位匹配b串前j位，用了k个子串且i与j是否匹配时的答案
转移方程：
//1.
f[0][0][0][0]=1;
f[1][0][0][0]=1;
for(i)
for(j)
for(k)
if(a[i]==b[j]){
f[i][j][k][1]=f[i-1][j-1][k][1]+f[i-1][j-1][k-1][1]+f[i-1][j-1][k-1][0];
}else{
f[i][j][k][1]=0;
}
f[i][j][k][0]=f[i-1][j][k][0]+f[i-1][j][t][1];
//2.
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j)
for(int l=1;l<=k;++l)f[i%2][j][l][1]=f[i%2][j][l][0]=0;
if(a[i-1]==b[0])f[i%2][1][1][1]=1;
for(int j=1;j<=m;++j){
for(int l=1;l<=k;++l){
if(a[i-1]==b[j-1]){
f[i%2][j][l][1]=(f[i%2][j][l][1]+f[(i-1)%2][j-1][l-1][1]+f[(i-1)%2][j-1][l][1]+f[(i-1)%2][j-1][l-1][0])%P;
}else f[i%2][j][l][1]=0;
f[i%2][j][l][0]=(f[i%2][j][l][0]+f[(i-1)%2][j][l][1]+f[(i-1)%2][j][l][0])%P;
}
}
}
注意需要第二种方法需要清零。
P2389
与P2679十分类似。少了一维，不用滚动。并且成了取最大值。 用f[i][j][0/1]表示用了j段，第i位是否取的答案。 转移方程：
//memset(f,-0x3f,sizeof f);
f[0][0][0]=0;
f[0][0][1]=0;
//f[1][0][0]=0;
//f[1][0][1]=0;
int ans=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=k;++j){
int max1=max(f[i-1][j][1],max(f[i-1][j-1][1],f[i-1][j-1][0]));
f[i][j][1]=max(f[i][j][1],max1+a[i]);
int max2=max(f[i-1][j][0],f[i-1][j][1]);
f[i][j][0]=max(f[i][j][0],max2);
ans=max(ans,max(f[i][j][0],f[i][j][1]));
}
}
~~所以不就是初始化为零吗~~
数字类计数
P7961
1) 第三维维护整体(加上第四维进位)的\(1\)的个数不好，因为可能会出现转移时第三位减少的情况，这样就可能溢出。
2) 快速幂不需要，直接预处理就行了。
3) 这种状态设计第一维到\(m+1\)就已经包含了所有状态，不能再往回找了。
正确做法是设\(f[i][j][p][l]\)表示考虑完第\(i\)个\(a_i\)，一共用了\(j\)个\(a\),当前不包括\(l\)一共\(p\)个\(1\),以及进位数\(l\).
因为每次都会将\(l/2\),并且每次\(l\)都不超过\(n\),所以每次枚举\(l\)到\(\frac n2\)即可。
这样只要在统计答案时将\(l\)的\(1\)的个数再加回来即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
const int N=33,M=110,P=998244353;
int f[M][N][N][20];
int C[N][N];
int v[M],num[N],pv[M][N];
int n,m,k;
inline int getnum(int i) {
int ans=0;
while(i)ans+=(i&1),i>>=1;
return ans;
}
void init() {
for(int i=0; i<=n; ++i) {
C[i][0]=1;
for(int j=1; j<=i; ++j)C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
}
for(int i=0; i<=n; ++i)num[i]=getnum(i);
for(int i=0;i<=m;++i){
pv[i][0]=1;
for(int j=1;j<=n;++j)pv[i][j]=(pv[i][j-1]*v[i])%P;
}
}
int dp() {
f[0][0][0][0]=1;
for(int i=0; i<=m; ++i)
for(int j=0; j<=n; ++j)
for(int p=0; p<=k; ++p)
for(int l=0; l<=(n>>1); ++l)
for(int q=0; q+j<=n; ++q) {
int tmp=((f[i][j][p][l]*pv[i][q]%P)*C[n-j][q])%P;
f[i+1][j+q][p+(q+l&1)][(l+q)>>1]=(f[i+1][j+q][p+(q+l&1)][(l+q)>>1]+tmp)%P;
}
int ans=0;
for(int p=0; p<=k; ++p)
for(int l=0; l<=(n>>1); ++l)
if(p+num[l]<=k)ans=(ans+f[m+1][n][p][l])%P;
return ans;
}
signed main() {
//freopen("sequence2.in","r",stdin);
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=0; i<=m; ++i)scanf("%lld",&v[i]);
init();
printf("%lld",dp());
return 0;
}
P1633
我们可以设一个五维的状态，f[i][j][k][l][0/1],表示X中有i个1，Y中有j个1，Z中有k个1，当前比较到了第l位，且Z的第l位是0还是1.
对于X和Y的第l位，有两种选择，就是填0或1，所以有如下转移：
f[i][j][k][l][0]+0 ->f[i][j][k][l+1][0] //0 0
+(1ll<<l-1) ->f[i][j+1][k+1][l+1][0] //0 1
+(1ll<<l-1) ->f[i+1][j][k+1][l+1][0] //1 0
+(1ll<<l) ->f[i+1][j+1][k+1][l+1][1] //1 1
f[i][j][k][l][1]+0 ->f[i][j][k][l+1][0] //0 0
+(1ll<<l-1) ->f[i][j+1][k][l+1][1] //0 1
+(1ll<<l-1) ->f[i+1][j][k][l+1][1] //1 0
+(1ll<<l) ->f[i+1][j+1][k+1][l+1][1] //1 1
举个例子，对于1111和11111这两种第l位分别是0和1的情况：~~(01111前导零不用管，只是表示第l位为0而已)~~
//左->右为低位->高位
l l
11110 ->111100
i 0
j 0
11110 ->111110
i 0
j 1
11110 ->111110
i 1
j 0
11110 ->111111
i 1
j 1
l l
11111 ->111110
i 0
j 0
11111 ->111101
i 0
j 1
11111 ->111101
i 1
j 0
11111 ->111111
i 1
j 1
边界是\(f[0][0][0][1][0]=0\),l从1开始.
对输入的a,b,c求出ll,na,nb,nc那么最终答案为\(\min(f[na][nb][nc][0,1,...,ll][0,1])\)
注：
\(f[i][j][k][l][0]+2^{l-1}\)不能转移给\(f[i][j+1][k+1][l][1]\),而是转移给\(f[i][j][k+1][l+1][0]\)
因为l没有移动位置，下次还是在第l位加1，所以会出现X或Y同一位加了两次1，出现错误。
~~其实l那一维可以滚存的，但我懒~~
Code:
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
const int N=33,INF=5e18;
int f[N][N][N][N][2];
int n,a,b,c,na,nb,nc,la,lb,lc,ll;
void init() {
memset(f,0x3f,sizeof f);
na=0;nb=0;nc=0;la=0;lb=0;lc=0;
while(a) {
if(a&1)na++;
la++;
a>>=1;
}
while(b) {
if(b&1)nb++;
lb++;
b>>=1;
}
while(c) {
if(c&1)nc++;
lc++;
c>>=1;
}
ll=max(la,max(lb,lc));
}
void work() {
f[0][0][0][1][0]=0;
for(int i=0; i<=na; ++i) {
for(int j=0; j<=nb; ++j) {
for(int k=0; k<=nc; ++k) {
for(int l=1; l<=ll; ++l) {
f[i][j][k][l+1][0]=min(f[i][j][k][l+1][0],min(f[i][j][k][l][0],f[i][j][k][l][1]));
f[i+1][j+1][k+1][l+1][1]=min(f[i+1][j+1][k+1][l+1][1],min(f[i][j][k][l][0],f[i][j][k][l][1])+(1ll<<l));//注意写法，1ll<<l要加括号
f[i][j+1][k+1][l+1][0]=min(f[i][j+1][k+1][l+1][0],f[i][j][k][l][0]+(1ll<<l-1));
f[i+1][j][k+1][l+1][0]=min(f[i+1][j][k+1][l+1][0],f[i][j][k][l][0]+(1ll<<l-1));
f[i][j+1][k][l+1][1]=min(f[i][j+1][k][l+1][1],f[i][j][k][l][1]+(1ll<<l-1));
f[i+1][j][k][l+1][1]=min(f[i+1][j][k][l+1][1],f[i][j][k][l][1]+(1ll<<l-1));
}
}
}
}
}
signed main() {
scanf("%lld",&n);
for(int i=1; i<=n; ++i) {
scanf("%lld%lld%lld",&a,&b,&c);
init();//初始化
work();//dp
int ans=INF;
for(int i=0; i<=ll; ++i) {
int tmp1=f[na][nb][nc][i][0],cnt1=0;
int tmp2=f[na][nb][nc][i][1],cnt2=0;
while(tmp1>0)tmp1>>=1,cnt1++;
while(tmp2>0)tmp2>>=1,cnt2++;
if(cnt1<=ll && cnt1>0)ans=min(ans,f[na][nb][nc][i][0]);//所有满足条件的数中取最小值
if(cnt2<=ll && cnt2>0)ans=min(ans,f[na][nb][nc][i][1]);
}
if(ans==INF)printf("-1\n");
else printf("%lld\n",ans);
}
return 0;
}
概率dp
P1769
可以发现每个人的比赛路程就是一颗完全二叉树，所以按照线段树建图的方式预处理出每一轮每个人对战的所有可能对手的编号。
之后，每个人都有一个赢到第\(j\)层的概率，每个对手也有赢到第\(j\)层的概率，则第\(i\)个人赢下第\(j\)层获胜的总概率为：
\[
f[i][j]=\sum_{t=l}^r f[i][j-1]*f[t][j-1]* a[i][t]/100.0;
\]
最后统计谁赢到最后的总概率最大且编号最小即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define db double
using namespace std;
const int N=1100;
db f[N][N],a[N][N];
int n,k;
int kp[N],h[N][N];
struct node{
int l,r;
}g[N<<2];
void init(){
kp[0]=1;
for(int i=1;i<=k;++i)kp[i]=kp[i-1]<<1;
}
void build(int k,int i,int l,int r){
g[i].l=l,g[i].r=r;
for(int j=l;j<=r;++j)h[j][k]=i;
if(l==r){
return;
}
int mid=l+r>>1;
build(k+1,i<<1,l,mid);
build(k+1,i<<1|1,mid+1,r);
}
int main(){
scanf("%d",&k);
init();
n=kp[k];
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)scanf("%lf",&a[i][j]);
build(1,1,1,n);
for(int i=1;i<=n;++i)f[i][0]=1.0;
for(int j=1;j<=k;++j){
for(int i=1;i<=n;++i){
int tmp=h[i][k+1-j+1]^1;
for(int t=g[tmp].l;t<=g[tmp].r;++t){
f[i][j]+=f[i][j-1]*f[t][j-1]*a[i][t]/100.0;
}
}
}
db ans=0;
int pos=0;
for(int i=1;i<=n;++i){
if(ans<f[i][k]){
pos=i;
ans=f[i][k];
}
}
printf("%d",pos);
return 0;
}
/*
2
0 90 50 50
10 0 10 10
50 90 0 50
50 90 50 0
*/
DAG上dp
P3953
这道题的无解情况就是当一条可行路径上包含了一个零环时,输出\(-1\)。
设\(f[i][k]\)表示走到第\(i\)个点，并且还有\(k\)的时间可以浪费的路径总条数。
每次转移相当于浪费了\(dis[u]+w-dis[v]\)的时间。
注意如果出现了非零的环，那么每转一圈都有不同状态的出现，所以不用判断\(-1\);但是因为零环转一圈没有新的贡献，所以要判断。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
typedef pair<int,int> PI;
const int N=2e5+10,M=55;
int T,n,m,u,v,w,K,P,cnt[2];
int head[2][N],dis[2][N],vis[N],flg[N][M],f[N][M];
struct node {
int v,w,nxt;
} e[2][N<<1];
void add(int u,int v,int w,int t) {
e[t][++cnt[t]].v=v,e[t][cnt[t]].w=w,e[t][cnt[t]].nxt=head[t][u],head[t][u]=cnt[t];
}
void dij(int t,int o) {
memset(dis[o],0x3f,sizeof dis[o]);
memset(vis,0,sizeof vis);
dis[o][t]=0;
set<PI> s;
s.insert(make_pair(0,t));
while(s.size()) {
set<PI>::iterator it=s.begin();
u=it->second;
s.erase(*it);
if(vis[u])continue;
vis[u]=1;
for(int i=head[o][u]; ~i; i=e[o][i].nxt) {
int v=e[o][i].v,w=e[o][i].w;
if(dis[o][v]>dis[o][u]+w) {
dis[o][v]=dis[o][u]+w;
if(!vis[v])s.insert(make_pair(dis[o][v],v));
}
}
}
}
int dfs(int u,int k) {
if(k<0 || k>K)return 0;
if(flg[u][k]) {//出现了环,并且因为走过一个环后k没有变化，说明这个环一定是个零环。
if(dis[0][u]+dis[1][u]<=dis[0][n]+K) {
flg[u][k]=0;
return -1;
} else if(flg[u][k]>=2) {//同一个零环又转了一圈，说明所有换上的点都已经用上面的语句判断过了，直接return
return 0;
}
}
if(f[u][k]!=-1)return f[u][k];
flg[u][k]++;
int res=0;
if(u==n)res=1;
for(int i=head[0][u]; ~i; i=e[0][i].nxt) {
int v=e[0][i].v,w=e[0][i].w;
int tmp=dfs(v,k-(dis[0][u]+w-dis[0][v]));
if(tmp==-1) {
flg[u][k]--;
return -1;
}
res=(res+tmp)%P;
}
flg[u][k]--;
return f[u][k]=res;
}
int main() {
scanf("%d",&T);
while(T--) {
memset(head,-1,sizeof head);
cnt[0]=cnt[1]=-1;
scanf("%d%d%d%d",&n,&m,&K,&P);
for(int i=1; i<=m; ++i) {
scanf("%d%d%d",&u,&v,&w);
add(u,v,w,0);
add(v,u,w,1);
}
dij(1,0);
dij(n,1);
memset(f,-1,sizeof f);
memset(flg,0,sizeof flg);
printf("%d\n",dfs(1,K));
}
return 0;
}