T1:火车站内往往设有一些主干线分叉出去的铁路支路,供火车停靠,以便上下客或装载货物铁路支路有一定长度;火车也有一定的长度,且每列火车的长度相等.假设某东西向的铁路上,有一小站.该站只有一条铁路支路可供火车停靠,并且该铁路支路最多能容纳 M 辆火车为了火车行驶的通畅,该站只允许火车自东方进站,自西方出站,且先进站的火车必须先出站,否则,站内火车将发生堵塞该火车站工作任务繁忙.每天都有 N 辆自东方驶向西方的火车要求在预定时刻进站,并在站内作一定时间的停靠.为了满足每辆进站火车的要求,小站的调度工作是井井有条地开展.在小站每天的工作开始前,小站工作人员须阅读所有火车的进站申请,并决定究竞接受哪些火车的申请.而对于不能满足要求的火车,小站必须提前通知它们,请它们改变行车路线,以免影响正常的铁路运输工作.由于火车进站、出站的用时可以忽略不计,小站允许几辆火车同时进站或出站,且小站工作人员可以任意安排这些火车进站的先后排列次序.小站的工作原则是尽量地满足申请火车的要求请你编一个程序,帮助工作人员考察某天所有火车的进站申请,计算最多能满足多少火车的要求.
S1:显然当m=1时就是贪心决策的"活动安排".要总结一下对于区间问题,不要随意用[ 0/1 ]表示选不选,可能是本人太菜了,这样推只成功过一次.回归本题,我们按进站时间sort(如果进站时间相同则按出站时间排序),再分m=1/2/3来讨论.当m=1时,可以贪心,也可dp.我们设f [ i ]表以第 i 辆车开头能合法最长车辆个数,显然f[ i ]=max{f[ j ]+1}(len[ j ].L>len[ i ].R),注意初始化f[ i ]=1.当m = 2,我们用f[ i ][ j ]表示以第 i辆为第 1 辆车,第 j 辆为第 2 辆车为开头能合法最长的车辆个数,f[ i ][ j ]=max{f[ j ][ k ]+1},这时注意i,j,k要保证i,j,k先进先出且k要等i出站再进站.当m = 3,f[ i ][ j ][ k ]=max{f[ j ][ k ][ g ]+1;}注意i, j,k先进先出,j,k,g先进先出,且g在i出站后进站.以集合结尾几个元素代表集合可以联系练习T3.
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; #define re register int n,m,f1[101],f2[101][101],f3[101][101][101]; struct bian{ int L,R; }len[110]; bool cmp(bian a,bian b){ if(a.L==b.L) return a.R<=b.R; else return a.L<b.L; } void work1() { int ans=0; for(re int i=n;i>=1;--i) for(re int j=i+1;j<=n;++j) if(len[j].L>=len[i].R){ if(!f1[j]) f1[j]=1; f1[i]=max(f1[i],f1[j]+1); ans=max(f1[i],ans); } printf("%d",ans); } void work2() { int ans=0; for(re int i=n;i>=1;--i) for(re int j=i+1;j<=n;++j){ if(len[j].R<len[i].R) continue; if(!f2[i][j]) f2[i][j]=2; for(re int k=j+1;k<=n;++k){ if(len[k].R<len[j].R||len[k].L<len[i].R) continue; if(!f2[j][k]) f2[j][k]=2; f2[i][j]=max(f2[i][j],f2[j][k]+1); ans=max(ans,f2[i][j]); } } printf("%d",ans); } void work3() { int ans=0; for(re int i=n;i>=1;--i) for(re int j=i+1;j<=n;++j) for(re int k=j+1;k<=n;++k){ if(len[j].R<len[i].R||len[k].R<len[j].R) continue; if(!f3[i][j][k]) f3[i][j][k]=3; for(re int g=k+1;g<=n;++g){ if(len[g].R<len[k].R||len[g].L<len[i].R) continue; if(!f3[j][k][g]) f3[j][k][g]=3; f3[i][j][k]=max(f3[i][j][k],f3[j][k][g]+1); ans=max(f3[i][j][k],ans); } } printf("%d",ans); } int main() { freopen("train.in","r",stdin); freopen("train.out","w",stdout); scanf("%d%d",&n,&m); for(re int i=1;i<=n;++i) scanf("%d%d",&len[i].L,&len[i].R); sort(len+1,len+1+n,cmp); if(m==1){work1();return 0;} else if(m==2){work2();return 0;} else {work3();return 0;} return 0; }
T2:给定一具有 N 个顶点(从 1 到 N 编号)的凸多边形,每个顶点的权均已知。问如何把这个凸多边形划分成 N-2 个互不相交的三角形,使得这些三角形顶点的权的乘积之和最小.
S2:显然的区间dp,由小区间的最值推大区间的最值.但有一点麻烦的是如果我们设f[ i ][ j ]代表区间[ i , j ]点最成多边形的乘积之和最小,在枚举分割点k时我们发现无法用f[ i ][ j ]去表示不是连续点组成的多边形(如①③④组成的三角形),自己还想用map求判断每种多边形,显然这样n!数量要爆long long的.看了题解方程f[ i ][ j ]=min(f[ i ][ k ]+f[ k ][ j ]+val[ i ]*val[ j ]*val[ k ]).发现这样转移能巧妙地将无法表示的多边形直接计算出来,差了转换的思想.
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define re register #define LL long long long long n,val[110],f[110][110]; long long getv(LL x,LL y,LL z){return val[x]*val[y]*val[z];} int main() { freopen("division.in","r",stdin); freopen("division.out","w",stdout); scanf("%lld",&n); for(re LL i=1;i<=n;++i) scanf("%lld",&val[i]); memset(f,0x7f,sizeof(f)); for(re LL len=2;len<=n;++len) for(re LL i=1;i+len-1<=n;++i){ LL j=i+len-1; if(j==i+1) f[i][j]=0; for(re LL k=i+1;k<=j-1;++k) f[i][j]=min(f[i][j],f[i][k]+f[k][j]+getv(i,k,j)); } printf("%lld",f[1][n]); return 0; }
T3:加分二叉树
S3:我们会发现对于区间[ i , j ],根结点k是决定同一中序不同形态树的关键.我们设f[ i ][ j ]表示区间[ i, j ]最高加分.我们枚举根节点k,f[ i ][ j ]=max{f[ i ][ k - 1]+f[ k + 1 ][ j ] + val[ k ]},注意k要讨论i,j两个端点情况.再用root数组记录转移关键点,记录区间根节点.我们不断递归区间根据根节点建树,在进行前序遍历即可.
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define re register #define LL long long long long n,s,val[110],vis[110],f[110][110],root[110][110]; struct shu{ LL x,ls,rs; }tree[110*2]; void add(LL fa,LL son,LL flag) { tree[fa].x=fa,tree[son].x=son; if(!flag) tree[fa].ls=son; else if(flag) tree[fa].rs=son; } LL build(LL l,LL r) { LL s=root[l][r]; if(l==r){ tree[l].ls=tree[l].rs=0; tree[l].x=l; return l; } else if(s==l){ LL rs=build(s+1,r); add(s,rs,1); tree[s].ls=0; return s; } else if(s==r){ LL ls=build(l,s-1); add(s,ls,0); tree[s].rs=0; return s; } else{ LL ls=build(l,s-1); LL rs=build(s+1,r); add(s,ls,0),add(s,rs,1); return s; } } void DLR(LL x) { printf("%lld ",x); if(tree[x].ls) DLR(tree[x].ls); if(tree[x].rs) DLR(tree[x].rs); } int main() { freopen("tree.in","r",stdin); freopen("tree.out","w",stdout); scanf("%lld",&n); for(re LL i=1;i<=n;++i){ scanf("%lld",&val[i]); f[i][i]=val[i]; } for(re LL len=2;len<=n;++len) for(re LL i=1;i+len-1<=n;++i){ LL j=i+len-1; f[i][j]=max(f[i][j],f[i+1][j]+val[i]); f[i][j]=max(f[i][j],f[i][j-1]+val[j]); for(re LL k=i+1;k<=j-1;++k) f[i][j]=max(f[i][j],f[i][k-1]*f[k+1][j]+val[k]); } for(re LL len=2;len<=n;++len) for(re LL i=1;i+len-1<=n;++i){ LL j=i+len-1; if(f[i][j]==f[i+1][j]+val[i]) root[i][j]=i; else if(f[i][j]==f[i][j-1]+val[j]) root[i][j]=j; else for(re LL k=i+1;k<=j-1;++k) if(f[i][j]==f[i][k-1]*f[k+1][j]+val[k]){ root[i][j]=k; break; } } printf("%lld ",f[1][n]); s=build(1,n); DLR(s); return 0; }
T4:最长前缀
S4:DP水题.f[ i ]表示能不能用字符串组成前 i 个字符.这样我们对每个 长度i往前推已知的字符长度len,如果f[ i - len ]合法则继承更新.
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define R register string s[110]; char t[500010]; int n,lent,flag,lens[110],f[500010]; int main() { freopen("prefix.in","r",stdin); freopen("prefix.out","w",stdout); scanf("%d",&n); for(R int i=1;i<=n;++i){ scanf("%d",&lens[i]); cin>>s[i]; } scanf("%s",t+1); lent=strlen(t+1); --lent; f[0]=1; for(R int i=1;i<=lent;++i){ for(R int j=1;j<=n;++j){ int len=lens[j]; int L=i-len,sur=0; flag=1; if(L<0||f[L]==0) continue; ++L; for(R int k=L;k<=i;++k) { if(s[j][sur]!=t[k]){ flag=0; break; } ++sur; } if(flag){ f[i]=1; break; } } } for(R int i=lent;i>=1;--i) if(f[i]){ printf("%d",i); return 0; } printf("0"); return 0; }