动态规划经典模型

ACM程序设计9.常见DP类型2023/1/311BracketsPOJ2955大意给你一个括号序列，求最长合法括号子序列的长度(序列长度不超过100)

2023/1/312SampleInputSampleOutput((()))()()()([]]))[)(([][][)end66406问题思路典型区间DP模型如果找到一对匹配的括号[xxx]oooo，就把区间分成两部分，一部分是xxx，一部分是oooo，然后以此递归直到区间长度为1或者为22023/1/313状态转移方程dp[i][j]表示区间[i,j]之间的最长合法括号子序列长度dp[i][j]=min{dp[i+1][j], dp[i+1][k-1]+dp[k+1][j]+1(i<=k<=j&&i和k是一对匹配的括号)}2023/1/3142023/1/315#defineN111intdp[N][N];charstr[N];intmatch(intx,inty){ returnstr[x]=='('&&str[y]==')'|| str[x]=='['&&str[y]==']'|| str[x]=='{'&&str[y]=='}';}intdfs(ints,inte){ inti,ret,t; if(e<s)return0; if(e==s)returndp[s][e]=0; if(e-s==1)returndp[s][e]=match(s,e); if(dp[s][e]!=-1)returndp[s][e]; ret=dfs(s+1,e); for(i=s+1;i<=e;i++)if(match(s,i)){ t=dfs(s+1,i-1)+dfs(i+1,e)+1; if(t>ret)ret=t; } returndp[s][e]=ret;}intmain(){ inti,j,k,n; while(gets(str),str[0]!='e'){ n=strlen(str); memset(dp,-1,sizeof(dp)); dfs(0,n-1); printf("%d\n",dp[0][n-1]*2); } return0;}CollectingBugsPOJ2096题意一个软件有s个子系统，会产生n种bug某人一天发现一个bug,这个bug属于一个子系统，属于一个分类每个bug属于某个子系统的概率是1/s,属于某种分类的概率是1/n问发现n种bug,每个子系统都发现bug的天数的期望。2023/1/316思路dp[i][j]表示目前已经找到i种bug,j个子系统的bug，达到目标状态的期望天数显然，dp[n][s]=0;答案是dp[0][0];dp[i][j]可以转化成以下四种状态:dp[i][j],发现一个bug属于已经有的i个分类和j个系统。概率为(i/n)*(j/s);dp[i][j+1],发现一个bug属于已有的分类，不属于已有的系统.概率为(i/n)*(1-j/s);dp[i+1][j],发现一个bug属于已有的系统，不属于已有的分类,概率为(1-i/n)*(j/s);dp[i+1][j+1],发现一个bug不属于已有的系统，不属于已有的分类,概率为(1-i/n)*(1-j/s);2023/1/317状态转移方程2023/1/3182023/1/319#defineFD(i,n)for(i=(n)-1;i>=0;i--)#defineN1002doubledp[N][N];intmain(){inti,j,n,s;while(scanf("%d%d",&n,&s)!=EOF){dp[n][s]=0.0;FD(i,n+1)FD(j,s+1){if(i==n&&j==s)continue;dp[i][j]=i*(s-j)*dp[i][j+1]+ (n-i)*j*dp[i+1][j]+ (n-i)*(s-j)*dp[i+1][j+1]+ n*s;dp[i][j]/=(n*s-i*j);}printf("%.4f\n",dp[0][0]);}return0;}概率DP小结概率DP主要用于求解期望、概率等题目。转移方程有时候比较灵活。一般求概率是正推，求期望是逆推。

推荐几篇NOI论文：《信息学竞赛中概率问题求解初探》《浅析竞赛中一类数学期望问题的解决方法》《有关概率和期望问题的研究》2023/1/3110BombHDU3555题意从1到N中包含49子序列的数的数目From1to500,thenumbersthatincludethesub-sequence"49"are"49","149","249","349","449","490","491","492","493","494","495","496","497","498","499",sotheansweris15.2023/1/3111数位前面加一个数码含49的含49的，前面可以加0-9不含49的，但是首位是9的可以加4不含49的不含49的，前面可以加0-9;去掉加了以后前两位是49的。2023/1/3112经典数位DP状态表示dp[i][0]表示i位长，含“49”的数的数目dp[i][1]表示i位长，不含“49”的数的数目状态转移dp[i][0]=dp[i-1][0]*10+dp[i-2][1]dp[i][1]=dp[i-1][1]*10–dp[i-2][1]边界条件dp[0][1]=1,dp[1][1]=102023/1/3113数位表位数含49不含49101021993209804299970153970960306494019505997590040940996086850999931490019779199509220800502023/1/3114统计n=0ak-1…a0第i位可以取1到ai的数码ans+=ai*dp[i][0]如果前面已经存在“49”，那么i长的不含49的也需要加入,而第i位可以取1到ai的数码ans+=ai*dp[i][1]如果前面没有存在49的数码，且ai>4,加入dp[i-1][1]ans+=dp[i-1][1]判断a[i+1,i]==49,设置出现标志，计算下一个数码如果已经存在49，那么490…0也是解，ans++2023/1/3115统计举例494*dp[1][0]+9*dp[0][0]+1=15485*dp[2][0]+dp[1][1]+4*dp[1][0]+8*dp[0][0]=5*1+10=1549104*dp[3][0]+9*dp[2][0]+dp[1][1]+1*dp[1][0]+dp[1][1]+0*dp[0][0]+1=4*20+9*1+10+1*0+10+0*0+1=1102023/1/3116idp[i][0]dp[i][1]10102199320980429997012023/1/3117#defineN20LLdp[N][2]; voidinit(){inti;dp[0][1]=1;dp[1][1]=10;

for(i=2;i<N;i++){dp[i][0]=dp[i-1][0]*10+dp[i-2][1];dp[i][1]=dp[i-1][1]*10-dp[i-2][1];}}intmain(){inti,len,tag,digit[N],cas;LLans,n;

init();scanf("%d",&cas);while(cas--){scanf("%I64d",&n);for(len=0;n;n/=10)digit[len++]=n%10;digit[len]=0;ans=0;tag=0;for(i=len-1;i>=0;i--){ans+=dp[i][0]*digit[i];if(tag)ans+=dp[i][1]*digit[i];elseif(digit[i]>4&&i)ans+=dp[i-1][1];if(digit[i+1]==4&&digit[i]==9)tag=1;}printf("%I64d\n",ans+tag);}

return0;}数位DP小结一般题目形式为统计一个区间内符合某些数码之间关系条件的数的个数一般思路先计算L长数码中的符合和不符合的个数（DP）从高位到低位，按位统计（DP）有些题可能需要使用大数（Java）2023/1/3118炮兵阵地POJ1185一个N*M方格组成的矩阵，每个方格可以放大炮用P表示，不可以放大炮用H表示，大炮可以攻击半径为2的十字，让放最多的大炮，大炮之间不会互相攻击。N<=100M<=102023/1/3119分析如果我们从上到下安排炮位，那么炮是否受到攻击，只和当前行的前两行相关。因为M很小(M<=10),我们使用10位2进制表示一行炮位的状态，1表示有炮，0表示无炮状态表示dp[i][Si][Si-1]表示第i行，其状态为Si,第i-1行的状态为Si-1时的最多炮位数(i>=2)dp[1][S1][S0]=cnt(S1)2023/1/3120s1中1的个数状态转移dp[i][Si][Si-1]=max{dp[i-1][Si-1][Si-2]+cnt(Si)}合法的状态mask=(Si-1|Si-2|Mi)mask&Si

为0表示合法时间复杂度O(N23M)100*230

太大，TLE2023/1/3121进一步优化Si

必须合法，那么任意两个1之间距离需要大于等于2,合法状态只有60个。f(n)=f(n-3)+f(n-1)f(1)=2,f(2)=3,f(3)=4f(10)=60先预处理出所有的合法状态及其1的个数时间复杂度为O(N*|S|3)2.16*1072023/1/31222023/1/3123intdp[N][M][M],s[M],c[M],lmt[10],map[N],n,m;intok(unsignedintx){ intt; if(x&x<<1)return0; if(x&x<<2)return0; return1;}intcnt(unsignedintx){ intt; inta[8]={0,1,1,2,1,2,2,3}; for(t=0;x;x>>=3)t+=a[x&7]; returnt;}voidinit(){ inti,j=1,k=0; for(i=0;i<(1<<10);i++)if(ok(i)){ s[k]=i; c[k]=cnt(i); if(i>((1<<j)-1))lmt[j-1]=k,j++; k++; } lmt[9]=M; }2023/1/3124voidsolve(){ inti,j,k,t,mask,tmp,ans=0;

m=lmt[m-1]; memset(dp,0,sizeof(dp)); FU(j,m)if(!(map[1]&s[j])){ FU(k,m)dp[1][j][k]=c[j]; } for(i=2;i<=n;i++){ FU(j,m)FU(k,m)FU(t,m){ mask=s[k]|s[t]|map[i]; if(mask&s[j])continue; tmp=dp[i-1][k][t]+c[j]; if(tmp>dp[i][j][k])dp[i][j][k]=tmp; }

} FU(j,m)FU(k,m)if(dp[n][j][k]>ans)ans=dp[n][j][k]; printf("%d\n",ans);}状压DP小结使用位表示状态，常见于在集合上的DP一般常见某一维很小（使用位压缩存储表示集合）如果状态值大于2，可能需要使用3进制或者4进制注意转移时状态的合法性2023/1/3125BalancingActPOJ1655题意一棵树，找到一个点,其所有的子树中最大的子树节点最少。节点1，其所有子树最大的子树节点数为22023/1/3126树一种数据结构定义由n(n>=0)个节点的组成的集合没有节点，被称为空树非空树，一个特定节点被称为根节点（root）剩下的n-1个点，被分成若干个不相交的集合这些集合也是树，被称为子树2023/1/3127一些术语根节点子树叶子节点孩子节点父节点兄弟节点树高2023/1/3128树的一些性质n个节点，n-1条边无环，连通任意两点之间有且仅有一条路2023/1/3129树的表示孩子兄弟父节点并查集里使用过用邻接表这是表示图的数据结构树是稀疏图2023/1/3130图的表示2023/1/3131邻接表多个链表组成实现方式vector<int>G[N];这种方式可能会因为vector的容量扩展导致TLE前向星邻接表是不是很像Hash时候的链地址法？实现多个链表的一种常见实现方式。2023/1/3132分析如果以P为根节点，那么存在其孩子数+1棵子树dp[i]表示以节点i作为根节点的最大子树节点数cnt[i]表示在原树里以节点i作为根节点的子树的节点数dp[p]=max{cnt[Ci],n-cnt[p]}cnt[p]=sum{cnt[Ci]}+1cnt[leaf]=12023/1/3133举例2023/1/31342023/1/3135#defineN20000#definemax(x,y)((x)>(y)?(x):(y))intvectex[N];intvisit[N];intvn,en;struct_edge{ intto; intnext;}edge[N<<1];voidinitGraph(){ memset(vectex,-1,sizeof(vectex)); memset(visit,0,sizeof(visit)); en=0;}voidaddEdge(intfrom,intto){ edge[en].to=to; edge[e