# T1

N<=100000

… 嗯，水题…

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
using namespace std;
int q=0;char ch=' ';
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
return q;
}
int n,m;int a[100005],b[100005],c[100005];
int main()
{
int i,j,kl;
for(i=n;i>=1;i--){
kl=upper_bound(b+1,b+1+m,a[i])-b;
if(kl>m){b[++m]=a[i];}
else {b[kl]=a[i];}
}
printf("%d\n",m);m=0;
for(i=1;i<=n;i++){
kl=lower_bound(c+1,c+1+m,a[i])-c;
if(kl>m){c[++m]=a[i];}
else {c[kl]=a[i];}
}
printf("%d",m);
return 0;
}


#T2

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
using namespace std;
int m,T;long long n;
unsigned long long f[22][22],a[22][22],s[22];int fa[22][22];
void go(int i,int j){
if(j==1){printf("%lld ",a[1][i]);return;}
go(fa[i][j],j-1);printf("%lld ",a[fa[i][j]+1][i]);
}
int main()
{
int i,j,k,tot=0;
scanf("%d",&T);
while(T--){
scanf("%lld%d",&n,&m);tot=0;
memset(f,0,sizeof(f));
while(n){s[++tot]=n%10;n=n/10;}
for(i=1;i<=tot;i++)a[i][i]=s[tot-i+1];
for(i=1;i<=tot;i++){
for(j=i+1;j<=tot;j++)
a[i][j]=a[i][j-1]*10+a[j][j];
f[i][1]=a[1][i];
}
for(i=1;i<=tot;i++)
for(j=2;j<=m&&j<=i;j++)
for(k=j-1;k<i;k++){
unsigned long long kl=f[k][j-1]*a[k+1][i];
if(kl>f[i][j]){f[i][j]=kl;fa[i][j]=k;}
}
printf("%lld\n",f[tot][m]);
if(!f[tot][m]){
for(j=1;j<=m-1;j++)printf("%lld ",a[j][j]);
printf("%lld\n",a[m][tot]);continue;
}
go(tot,m);printf("\n");
}
return 0;
}


#T3
Peter 最近在 R 市开了一家快餐店，为了招揽顾客，该快餐店准备推出一种套餐，该套

100 个。

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
using namespace std;
int aa,bb,cc,p1,p2,p3,n,ans;
int t[12];
int f[12][102][102];
int main()
{
int i,j,k,j1,k1,kl;
scanf("%d%d%d",&aa,&bb,&cc);
scanf("%d%d%d",&p1,&p2,&p3);
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&t[i]);
int maxn=min(100/aa,min(100/bb,100/cc));//不超过 100 个，最多生产套餐数
memset(f,-1,sizeof(f));
f[0][0][0]=0;
for(i=1;i<=n;i++)
for(j=0;j<=maxn*aa;j++)
for(k=0;k<=maxn*bb;k++)
for(j1=0;j1<=j;j1++)
for(k1=0;k1<=k;k1++){
if(j1*p1+k1*p2>t[i]||f[i-1][j-j1][k-k1]==-1)continue;
if(f[i][j][k]>=maxn*cc)break;//剪枝
kl=(t[i]-j1*p1-k1*p2)/p3;
f[i][j][k]=max(f[i][j][k],f[i-1][j-j1][k-k1]+kl);
}
for(j=0;j<=maxn*aa;j++)
for(k=0;k<=maxn*bb;k++)
ans=max(ans,min(j/aa,min(k/bb,f[n][j][k]/cc)));
printf("%d",ans);
return 0;
}


#T4

Bi 的重量和价值分别为 Bwi 和 Bvi。

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m;
int f[10005];
int aw[105],bw[105],av[105],bv[105];
int main()
{
int i,j;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{scanf("%d%d%d%d",&aw[i],&av[i],&bw[i],&bv[i]);}
for(i=1;i<=n;i++)
for(j=m;j>=0;j--){
if(j>=aw[i])f[j]=max(f[j],f[j-aw[i]]+av[i]);
if(j>=bw[i])f[j]=max(f[j],f[j-bw[i]]+bv[i]);
}
printf("%d",f[m]);
return 0;
}