NOIP 考前DP 复习

POJ 2533 最长不降子序列

 #include <cstdio>

 const int Maxn=;

 int a[Maxn],Pos[Maxn],F[Maxn],n,Ans;

 inline int Max(int x,int y) {return x>y?x:y;}

 inline int Find(int x)

 {

     int l=,r=Ans,Res;

     while (l<=r)

     {

         int mid=(l+r)>>;

         if (a[Pos[mid]]<x) Res=mid,l=mid+;  else r=mid-;

     }

     return Res;

 }

 int main()

 {

     scanf("%d",&n);

     for (int i=;i<=n;i++) scanf("%d",&a[i]);

     F[]=; Pos[]=; Ans=;

     for (int i=;i<=n;i++)

     {

         int t=Find(a[i]);

         Pos[t+]=i;

         F[i]=t+;

         Ans=Max(Ans,F[i]);

     }

     printf("%d\n",Ans);

     return ;

 }

POJ 2533

BZOJ 3886

状压DP+贪心

 #include <cstdio>

 #include <cstring>

 const int Maxn=;

 const int Maxm=;

 const int Inf=0x3f3f3f3f;

 inline int Min(int x,int y) {return x>y?y:x;}

 inline int Max(int x,int y) {return x>y?x:y;}

 int n,m,f[<<Maxn],Ans=Inf;

 int Len[Maxn],P[Maxn],C[Maxn][Maxm];

 int find(int x,int id)

 {

     int l=,r=P[id];

     while (l<r)

     {

         int mid=(l+r+)>>;

         if (C[id][mid]<=x) l=mid;

         else r=mid-;

     }

     return l;

 }

 int main()

 {

     // freopen("c.in","r",stdin);

     scanf("%d%d",&n,&m);

     for (int i=;i<=n;i++)

     {

         scanf("%d%d",&Len[i],&P[i]);

         for (int j=;j<=P[i];j++) scanf("%d",&C[i][j]);

     }

     memset(f,-,sizeof(f)),f[]=;

     for (int i=;i<(<<n);i++)

     {

         if (f[i]==-) continue;

         if (f[i]>=m)

         {

             int j,k;

             for (j=,k=i;k;k-=(k&(-k))) j++;

             Ans=Min(Ans,j);

             continue;

         }

         for (int j=;j<=n;j++)

         {

             if (i&(<<(j-))) continue;

             int k=find(f[i],j);

             if (k==) continue;

             f[i|(<<(j-))]=Max(f[i|(<<(j-))],C[j][k]+Len[j]);

         }

     }

     printf("%d\n",Ans==Inf?-:Ans);

     return ;

 }

BZOJ 3886