T1:导弹拦截
S1:Q1为最长不上升子序列,Q2为求最长上升子序列.蒟蒻采用的是单调栈的做法,拿求最长上升子序列来说,将a[ 1 ]先入栈,再维护单调上升序列,若大于q[ lenth ],则入栈,若不大于则二分查找,找到单调栈中第一个比它大的数代替,虽然没找到严谨的证明,可以感性理解不断代替大的数的过程,使单调栈的最大值往小的方面发展,是更多数入站,lenth即为答案.Q2用到了Dilworth定理 :最少链划分 = 最长反链长度.
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define e exit(0) #define R register int n,len,h[100010],q[100010]; int main() { freopen("missile.in","r",stdin); freopen("missile.out","w",stdout); scanf("%d",&n); for(R int i=1;i<=n;++i) scanf("%d",&h[i]); q[++len]=h[n]; for(R int i=n-1;i>=1;--i){ if(h[i]>=q[len]) q[++len]=h[i]; else{ int id=lower_bound(q+1,q+1+len,h[i])-q; q[id]=h[i]; } } printf("%d ",len); memset(q,0,sizeof(q)); len=0; q[++len]=h[1]; for(R int i=2;i<=n;++i){ if(h[i]>=q[len]) q[++len]=h[i]; else{ int id=lower_bound(q+1,q+1+len,h[i])-q; q[id]=h[i]; } } printf("%d",len); return 0; }
T2:整数划分
S2:我们可以看出这是一个区间DP.我们设f[ i ][ j ]表示前i个数有j个乘号时的最大乘积j∈[ 0 , i-1 ].分割点k的位置枚举可以从j开始(第j个乘号即在第j个数的后面).f[ i ][ j ] = max{f[ k ][ j - 1]+getv( k +1 , i )}.getv函数即求区间这段数的大小.但在试题中我们还有求出怎么划分,记录分割点,用前驱数组到回去即可.
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define R register #define ll long long long long T,n,m,ans,lenth,deep,num[110],f[110][110],q[110],lastr[110][110][3]; void cf(long long x) { deep=0; long long len=0,mix[110]; while(x) { mix[++len]=x%10; x/=10; } for(R int i=len;i>=1;--i) num[++deep]=mix[i]; } long long getv(ll x,ll y) { long long sum=0; for(R ll i=x;i<=y;++i) sum=sum*10+num[i]; return sum; } int main() { freopen("separate.in","r",stdin); freopen("separate.out","w",stdout); scanf("%lld",&T); while(T--){ lenth=0; memset(f,0,sizeof(f)); memset(q,0,sizeof(q)); memset(num,0,sizeof(num)); memset(lastr,-1,sizeof(lastr)); scanf("%lld%lld",&n,&m); cf(n); for(R int i=1;i<=deep;++i) f[i][0]=getv(1,i); for(R int i=1;i<=deep;++i) for(R int j=1;j<=deep-1;++j) for(R int k=j;k<=i-1;++k) f[i][j]=max(f[i][j],f[k][j-1]*getv(k+1,i)); for(R int i=1;i<=deep;++i) for(R int j=1;j<=deep-1;++j) for(R int k=j;k<=i-1;++k) if(f[i][j]==f[k][j-1]*getv(k+1,i)){ lastr[i][j][0]=k; lastr[i][j][1]=j-1; lastr[i][j][2]=f[k][j-1]; } printf("%lld ",f[deep][m-1]); if(f[deep][m-1]==0){ for(R int i=1;i<=deep;++i) printf("%lld ",num[i]); printf(" "); continue; } long long lax=deep,lay=m-1; while(lax!=-1&&lay!=-1){ if(lastr[lax][lay][2]!=-1) q[++lenth]=lastr[lax][lay][2]; ll nowx=lastr[lax][lay][0],nowy=lastr[lax][lay][1]; lax=nowx,lay=nowy; } long long num=f[deep][m-1]/q[1]; for(R int i=1;i<=lenth-1;++i) q[i]=q[i]/q[i+1]; for(R int i=lenth;i>=1;--i) printf("%lld ",q[i]); printf("%lld ",num); } return 0; }
T3:Peter 最近在 R 市开了一家快餐店,为了招揽顾客,该快餐店准备推出一种套餐,该套餐由 A 个汉堡,B 个薯条和 C 个饮料组成.为了提高产量,Peter 从著名的麦当劳公司引进了 N 条生产线.所有的生产线都可以生产汉堡,薯条和饮料,由于每条生产线每天所能提供的生产时间是有限的、不同的,而汉堡,薯条和饮料的单位生产时间又不同.这使Peter 很为难,不知道如何安排生产才能使一天中生产的套餐产量最大.请你编一程序,计算一天中套餐的最大生产量.为简单起见,假设汉堡、薯条和饮料的日产量不超过100 个.
S3:没什么思路,只会f[i][A][B][C]的四维DP,显然时间空间都炸穿.看了题解,发现套餐的个数就是A,B,C中最小能组成的套餐数.我们设f[ k ][ i ][ j ]表示前k个选i个A,j个B时最多还能选多少个C.这里有个枚举的优化,我们确定套数的上限maxn=min ( 100/a,min( 100/b , 100/c ) ),那么要枚举的个数上限即为maxn*a 或 maxn * b.我们显然会有这样的DP方程:f[ k ][ i ][ j ]=max{f[ k - 1 ][ i - i1 ][ j - j1 ]+(p[ k ] - i1*a - j1*b)/c.}要注意f[ k - 1][ i -i1][ j -j1]的合法性,以及f[ k ][ i ][ j ]>=maxn*c要break.
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define R register int a,b,c,p1,p2,p3,n,t[12],f[12][110][110],ans,maxn; int main() { freopen("meal.in","r",stdin); freopen("meal.out","w",stdout); scanf("%d%d%d%d%d%d%d",&a,&b,&c,&p1,&p2,&p3,&n); for(R int i=1;i<=n;++i) scanf("%d",&t[i]); maxn=min(100/a,min(100/b,100/c)); memset(f,-1,sizeof(f)); f[0][0][0]=0; for(R int k=1;k<=n;++k) for(R int i=0;i<=maxn*a;++i) for(R int j=0;j<=maxn*b;++j) for(R int i1=0;i1<=i;++i1) for(R int j1=0;j1<=j;++j1) { if(f[k-1][i-i1][j-j1]!=-1&&t[k]-i1*p1-j1*p2>=0){ if(f[k][i][j]>=maxn*c) break; f[k][i][j]=max(f[k][i][j],f[k-1][i-i1][j-j1]+(t[k]-i1*p1-j1*p2)/p3); } } for(R int i=0;i<=maxn*a;++i) for(R int j=0;j<=maxn*b;++j) ans=max(ans,min(j/b,min(f[n][i][j]/c,i/a))); printf("%d",ans); return 0; }
T4:设有 n 种物品,记作 A1、A2、...、An,对应于每个 Ai(1<=i<=n)都有一个重量 Awi和价值 Avi (重量和价值都为正整数).另外,对应于每个 Ai,都有一件可代替它的“代品”Bi,
Bi 的重量和价值分别为 Bwi 和 Bvi.本题的任务是:选择这 n 件物品或其代用品的一个子集装进背包,使总重量不超过给定重量 TOT,同时使总价值 VAL 最高.装填的第 i 步,要么装入 Ai,要么装入 Bi,要么 Ai和 Bi 都不装.
S4:0/1背包的改动.我们用f[ i ][v][ 0/1/2 ]表示第i个不选,选A,选B,同时选入v大小的背包,转移显而易见.
#include<iostream> #include<cstdio> #include<cmath> using namespace std; #define R register int n,tot,f[101][10001][3]; struct box{ int w1,v1,w2,v2; }T[110]; int main() { freopen("box.in","r",stdin); freopen("box.out","w",stdout); scanf("%d%d",&n,&tot); for(R int i=1;i<=n;++i) scanf("%d%d%d%d",&T[i].w1,&T[i].v1,&T[i].w2,&T[i].v2); for(R int i=1;i<=n;++i) for(R int j=tot;j>0;--j) { int w1=T[i].w1,v1=T[i].v1,w2=T[i].w2,v2=T[i].v2; if(j>=w1){ f[i][j][1]=max(f[i][j][1],f[i-1][j-w1][1]+v1); f[i][j][1]=max(f[i][j][1],f[i-1][j-w1][2]+v1); f[i][j][1]=max(f[i][j][1],f[i-1][j-w1][0]+v1); } if(j>=w2){ f[i][j][2]=max(f[i][j][2],f[i-1][j-w2][1]+v2); f[i][j][2]=max(f[i][j][2],f[i-1][j-w2][2]+v2); f[i][j][2]=max(f[i][j][2],f[i-1][j-w2][0]+v2); } f[i][j][0]=max(f[i-1][j][1],max(f[i-1][j][2],f[i-1][j][0])); } printf("%d",max(f[n][tot][0],max(f[n][tot][1],f[n][tot][2]))); return 0; }