1 #include<cstdio> 2 #include<cstring> 3 #define MAXN 100005 4 int dp[MAXN][11];//第i秒第j个位置的馅饼数 5 int max1(int a,int b) 6 { 7     return a>b?a:b; 8 } 9 int max2(int a,int b,int c)10 {11     return a>b?(a>c?a:c):(b>c?b:c);12 }13 int main()14 {15     int n,x,t,T;16     while(~scanf("%d",&n))17     {18         if(n==0) break;19         T=0;20         memset(dp,0,sizeof(dp));21         for(int i=1;i<=n;i++)22         {23             scanf("%d%d",&x,&t);24             dp[t][x]++;25             if(T<t) T=t;//时间不一定递增的，找到最大的时间26         }27         for(int i=T;i>=0;i--)//从底往上一层一层的加28         {29             for(int j=0;j<=10;j++)30             {31                 if(j==0) dp[i][j]+=max1(dp[i+1][0],dp[i+1][1]);32                 else if(j==10) dp[i][j]+=max1(dp[i+1][9],dp[i+1][10]);33                 else dp[i][j]+=max2(dp[i+1][j+1],dp[i+1][j],dp[i+1][j-1]);34             }35         }36         printf("%d\n", dp[0][5]);//起始位置在537     }38     return 0;39 }

 1 #include<cstdio> 2 #include<cstring> 3 int n,k,a[25][15],dp[25][15]; 4 int abss(int a) 5 { 6     return a>0?a:-a; 7 } 8 int main() 9 {10     while(scanf("%d%d",&n,&k)!=EOF)11     {12         for(int i=1;i<=n;i++)13         {14             for(int j=1;j<=k;j++)15             {16                 scanf("%d",&a[i][j]);//第i秒第j个位置有老鼠17             }18         }19         memset(dp,0,sizeof(dp));20         int tmp,cur,ans=1000000;21         for(int i=n-1;i>=1;i--)//从下往上选最优22         {23             for(int j=1;j<=k;j++)24             {25                 tmp=1000000;26                 for(int m=1;m<=k;m++)27                 {28                     cur=abss(a[i][j]-a[i+1][m])+dp[i+1][m];29                     if(cur<tmp)30                     {31                         tmp=cur;32                     }33                 }34                 dp[i][j]+=tmp;35             }36         }37         for(int i=1;i<=k;i++)//最后在第一层中选出最小的38         {39             if(dp[1][i]<ans)40             {41                 ans=dp[1][i];42             }43         }44         printf("%d\n", ans);45     }46     return 0;47 }

 1 #include<cstdio> 2 #define MAXN 1010 3 #define LL long long 4 LL a[MAXN],dp[MAXN],ans; 5 int n; 6 int main() 7 { 8     while(scanf("%d",&n)!=EOF) 9     {10         if(n==0) break;11         for(int i=0;i<n;i++)12         {13             scanf("%lld",&a[i]);14         }15         for(int i=0;i<n;i++)16         {17             dp[i]=a[i];//dp[i]保存的是到i为止满足题意的和的最大值18         }19         for(int i=0;i<n;i++)20         {21             ans=0;22             for(int j=0;j<i;j++)//在i前面找到一个满足题意的且和最大的23             {24                 if(a[i]>a[j]&&dp[j]>ans)25                 {26                     ans=dp[j];27                 }28             }29             dp[i]+=ans;30         }31         ans=0;32         for(int i=0;i<n;i++)33         {34             if(dp[i]>ans)35                 ans=dp[i];36         }37         printf("%lld\n", ans);38     }39     return 0;40 }

 1 #include<cstdio> 2 #include<algorithm> 3 #define MAXN 1010 4 using namespace std; 5 struct mouse 6 { 7     int w,s,no,l,pre;//重量、速度、编号、以此老鼠为结尾的满足题意序列的最长长度、在满足题意序列中的前驱(用于输出路径) 8 }; 9 mouse mice[MAXN],tmp;10 bool cmp(mouse a,mouse b)11 {12     if(a.w==b.w) return a.s>b.s;13     return a.w<b.w;14 }15 bool cmp2(mouse a,mouse b)16 {17     return a.no<b.no;18 }19 int main()20 {21     int tot=0,cur,k;22     while(scanf("%d%d",&tmp.w,&tmp.s)!=EOF)23     {24         tmp.no=++tot;25         tmp.l=1;26         tmp.pre=tot;27         mice[tot]=tmp;28     }29     sort(mice+1,mice+tot+1,cmp);30     for(int i=1;i<=tot;i++)31     {32         cur=0; k=mice[i].no;33         for(int j=1;j<i;j++)34         {35             if(mice[j].w<mice[i].w&&mice[j].s>mice[i].s&&mice[j].l>cur)36             {37                 cur=mice[j].l;38                 k=mice[j].no;39             }40         }41         mice[i].l+=cur;42         mice[i].pre=k;43     }44     cur=0;k=0;45     for(int i=1;i<=tot;i++)46     {47         if(mice[i].l>cur)48         {49             cur=mice[i].l;50             k=mice[i].no;51         }52     }53     sort(mice+1,mice+tot+1,cmp2);54     printf("%d\n", cur);55     tmp=mice[k];56     int top=-1,print[MAXN];57     for(int i=1;i<=cur;i++)//最后拿个栈输出的58     {59         print[++top]=tmp.no;60         tmp=mice[tmp.pre];61     }62     while(top>-1)63     {64         printf("%d\n",print[top--]);65     }66     67 }

 1 #include<cstdio> 2 #include<cstring> 3 #define MAXN 1005 4 char str1[MAXN],str2[MAXN]; 5 int dp[MAXN][MAXN]; 6 int mmax(int a,int b) 7 { 8     return a>b?a:b; 9 }10 int main()11 {12     while(~scanf("%s",str1))13     {14         scanf("%s",str2);15         memset(dp,0,sizeof(dp));16         int n=strlen(str1);17         int m=strlen(str2);18         for(int i=1;i<=n;i++)//按着状态转移方程写就行了，也没什么细节...19         {20             for(int j=1;j<=m;j++)21             {22                 if(str1[i-1]==str2[j-1])23                 {24                     dp[i][j]=dp[i-1][j-1]+1;25                 }else26                 {27                     dp[i][j]=mmax(dp[i-1][j],dp[i][j-1]);28                 }29             }30         }31         printf("%d\n", dp[n][m]);32     }33     return 0;34 }

 1 #include<cstdio> 2 #include<cstring> 3 #define MAXN 510 4 #define REP(i,a,b) for(int i=a;i<b;i++) 5 int a[MAXN],b[MAXN],dp[MAXN],n,m,T,max; 6 int main() 7 { 8     scanf("%d",&T); 9     while(T--)10     {11         scanf("%d",&n);12         REP(i,0,n) scanf("%d",&a[i]);13         scanf("%d",&m);14         REP(i,0,m) scanf("%d",&b[i]);15         memset(dp,0,sizeof(dp));16         /*看不懂的建议自己先动手模拟一遍17           表面上dp[]是一维的，其实它代表的是dp[i,j]18           1 4 2 6 3 8 5 9 119           2 7 6 3 5 120           比如上面这两个序列：21           i=0:把dp[5]置为1,因为有相等的22           i=1:虽然在b[5]时，max=1了，但是b后面并没有4了，所以也没有更新23           i=2:把dp[0]置为124           i=3:这一步比较关键了，理解了就懂这个算法了 a[3]=625               j=0时，把max更新为1，这代表在6之前a里面已经有一个2与b里面的匹配了26               所以此时的max=1，如果在b里面2的后面还能找到一个6，那么就把dp[2]置为227               因为起码有个2 6是公共上升子序列了28           i=4......后面的一步步模拟 到i=6即a[6]=5的时候是最大的3 把dp[4]置为329           ...最后遍历一遍dp数组找到最大的值即为所求30         */31         REP(i,0,n) {32             max=0;33             REP(j,0,m) {34                 if(a[i]>b[j]&&dp[j]>max) max=dp[j];35                 if(a[i]==b[j]) dp[j]=max+1;36             }37         }38         max=0;39         REP(i,0,m) if(dp[i]>max) max=dp[i];40         printf("%d\n",max);41         if(T) printf("\n");42     }43     return 0;44 }

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 const int maxn=1001; 6 int a[maxn],b[maxn],dp[maxn]; 7 int n,m; 8 int LICS() 9 {10     int MAX,i,j;11     memset(dp,0,sizeof(dp));12     for(i=0;i<n;i++)13     {14         MAX=0;15         for(j=0;j<m;j++)16            {17            if(a[i]>b[j] && MAX<dp[j])18                MAX=dp[j];19            if(a[i]==b[j])20                dp[j]=MAX+1;21            }22     }23     MAX=0;24     for(i=0;i<m;i++)25         if(dp[i]>MAX)26          MAX=dp[i];27     return MAX;28 }29 int main()30 {31     int t,i;32     scanf("%d",&t);33     while(t--)34     {35         scanf("%d",&n);36         for(i=0;i<n;i++)37           scanf("%d",&a[i]);38         scanf("%d",&m);39         for(i=0;i<m;i++)40             scanf("%d",&b[i]);41         printf("%d\n",LICS());42     }43     return 0;44 }#include <iostream>45 #include <cstdio>46 #include <cstring>47 using namespace std;48 const int maxn=1001;49 int a[maxn],b[maxn],dp[maxn];50 int n,m;51 int LICS()52 {53     int MAX,i,j;54     memset(dp,0,sizeof(dp));55     for(i=0;i<n;i++)56     {57         MAX=0;58         for(j=0;j<m;j++)59            {60            if(a[i]>b[j] && MAX<dp[j])61                MAX=dp[j];62            if(a[i]==b[j])63                dp[j]=MAX+1;64            }65     }66     MAX=0;67     for(i=0;i<m;i++)68         if(dp[i]>MAX)69          MAX=dp[i];70     return MAX;71 }72 int main()73 {74     int t,i;75     scanf("%d",&t);76     while(t--)77     {78         scanf("%d",&n);79         for(i=0;i<n;i++)80           scanf("%d",&a[i]);81         scanf("%d",&m);82         for(i=0;i<m;i++)83             scanf("%d",&b[i]);84         printf("%d\n",LICS());85     }86     return 0;87 }

 1 #include<cstdio> 2 #include<cstring> 3 #define MAXN 1005 4 int a[MAXN],dp[MAXN],n,max;//这个dp[i]存的是以i为结尾的最长递增子序列的长度 5 int main() 6 { 7     while(scanf("%d",&n)!=EOF) 8     { 9         for(int i=0;i<n;i++) scanf("%d",&a[i]);10         memset(dp,0,sizeof(dp));11         for(int i=0;i<n;i++)12         {13             max=0;14             for(int j=0;j<i;j++)//转移方程dp[i]=max{dp[j]+1} 其中j要满足的a[i]>a[j]15             {16                 if(a[i]>a[j]&&dp[j]>max) max=dp[j];//因为要找到这个最大值 所以从0到i遍历了一遍17             }18             dp[i]=max+1;19         }20         for(int i=0;i<n;i++) max=max>dp[i]?max:dp[i];21         printf("%d\n",max);22     }23     return 0;24 }

 1 #include<cstdio> 2 #include<cstring> 3 #define MAXN 1005 4 int a[MAXN],dp[MAXN],n; 5 /* 6     这个版本的dp[i]存的就是a中长度为i的递增子序列末尾数的最小值 7     比较绕口 给个序列吧：2 1 4 3 5 数组下标从1开始 8     a[1]=2 dp[1]=2 9     a[2]=1 dp[1]=110     a[3]=4 dp[2]=411     a[4]=3 dp[2]=312     a[5]=5 dp[3]=513     最终dp更新到第几项 最长长度就是几 而不是dp里面存的数14     更详细的模拟过程可以看这个15     http://www.cnblogs.com/mengxm-lincf/archive/2011/07/12/2104745.html16     二分部分的代码借鉴了这个17     http://www.wutianqi.com/?p=185018 */19 int BSearch(int x,int k)20 {21     int low=1,high=k,mid;22     while(low<=high)23     {24         mid=(low+high)>>1;25         if(x>=dp[mid]) low=mid+1;26         else high=mid-1;27     }28     return low;29 }30 int main()31 {32     while(scanf("%d",&n)!=EOF)33     {34         for(int i=1;i<=n;i++) scanf("%d",&a[i]);35         memset(dp,0,sizeof(dp));36         int k=1; dp[k]=a[1];37         for(int i=2;i<=n;i++)38         {39             if(a[i]>dp[k]) dp[++k]=a[i];40             else dp[BSearch(a[i],k)]=a[i];41         }42         printf("%d\n",k);43     }44     return 0;45 }

 1 #include<cstdio> 2 #include<cstring> 3 #define MAXN 500010 4 #define REP(i,a,b) for(int i=a;i<b;i++) 5 #define MEM(a) memset(a,0,sizeof(a)) 6 int a[MAXN],dp[MAXN],n; 7 int BSearch(int x,int k) 8 { 9     int low=1,high=k,mid;10     while(low<=high)11     {12         mid=(low+high)>>1;13         if(x>=dp[mid]) low=mid+1;14         else high=mid-1;15     }16     return low;17 }18 int main()19 {20     int cases=0,x,y;21     while(~scanf("%d",&n))22     {23         REP(i,1,n+1) {24             scanf("%d%d",&x,&y);25             a[x]=y;26         }27         MEM(dp);28         int k=1; dp[k]=a[1];29         REP(i,2,n+1) {30             if(a[i]>dp[k]) dp[++k]=a[i];31             else dp[BSearch(a[i],k)]=a[i];32         }33         printf("Case %d:\n",++cases);34         printf("My king, at most %d road", k);//坑爹啊 road roads傻傻分不清楚35         if(k!=1) printf("s");36         printf(" can be built.\n\n");37     }38     return 0;39 }

 1 #include<cstdio> 2 #include<cstring> 3 #define MAXN 1005 4 int n,v,c[MAXN],w[MAXN],f[MAXN][MAXN]; 5 int mmax(int a,int b) 6 { 7     return a>b?a:b; 8 } 9 int main()10 {11     int T;12     scanf("%d",&T);13     while(T--)14     {15         scanf("%d%d",&n,&v);16         for(int i=1;i<=n;i++)17         {18             scanf("%d",&w[i]);19         }20         for(int i=1;i<=n;i++)21         {22             scanf("%d",&c[i]);23         }24         memset(f,0,sizeof(f));25         for(int i=1;i<=n;i++)//经典动规 f[i][j]表示把i件物品放入容量为j的背包中能获得的最大价值26         {27             for(int j=0;j<=v;j++)//这里j要从0开始，从1开始就WA，这一点我到现在也没理解，各位大神谁看到了给我解释一下...28             {29                 if(j>=c[i]) f[i][j]=mmax(f[i-1][j],f[i-1][j-c[i]]+w[i]);//按照转移方程写就OK了30                 else f[i][j]=f[i-1][j];31             }32         }33         printf("%d\n", f[n][v]);34     }35     return 0;36 }

 1 #include<cstdio> 2 #include<cstring> 3 #define MAXN 1005 4 int n,v,c[MAXN],w[MAXN],f[MAXN]; 5 int mmax(int a,int b) 6 { 7     return a>b?a:b; 8 } 9 int main()10 {11     int T;12     scanf("%d",&T);13     while(T--)14     {15         scanf("%d%d",&n,&v);16         for(int i=1;i<=n;i++)17         {18             scanf("%d",&w[i]);19         }20         for(int i=1;i<=n;i++)21         {22             scanf("%d",&c[i]);23         }24         memset(f,0,sizeof(f));25         /*26             状态转移方程是f[j]=max(f[j],f[j-c[i]]+w[i]) 代表背包容量为j的最大价值27             这里f是一维的，但是其实后面max里面的f[j]表示的是f[i-1,j]，要做到这一点需要以j从v到0的逆序方式遍历28             具体怎么理解呢，其实自己模拟一遍是最好的...29             我们知道，实质上01背包问题的状态转移方程是f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i])30             前面是不放第i件物品的策略，后面是放第i件物品的策略 但是要选择放策略的时候 31             需要的f[i-1][j-c[i]]这个值必须是没有放第i件物品计算出来的值，否则就不是01背包了，32             因为每件物品你都可能放了多件33             只有让j从v到0的遍历方式，才能保证在计算f[j]时用到的f[j-c[i]]是第i-1次的(即没有放第i件物品的)34             比如c[i] 1 2 3 4 5//代价35                 w[i] 5 4 3 2 1//价值36             如果j是从0到v的顺序遍历的，则算出来的dp[1]=5 在你算dp[2]的时候，此时调用的37             dp[j]=max(dp[j],dp[j-c[i]]+w[i]) 你会得到dp[2]=dp[2-1]+w[1]=1038             这个结果意味着容量为2的背包最大价值是10，而在01背包中这个值显然应该是4，原因就在于由于顺序遍历39             造成了在计算dp[2]时，放了两件第1件物品 这在01背包中是不允许的40             而采用逆序的方式则可以保证在计算dp[2]的时候，dp[1]还是0(在背包不要求装满的情况下，只要给dp初始化0就行)41             这样就能保证每个物品至多放一次 自己按照逆序模拟一遍就能体会到这个策略的正确性了42             ps：这里多说一句吧，其实按照j从0到v的方式遍历，刚好是另一种背包问题--完全背包的解法，这种背包问题中，43                 每个物品都有无限件可选，也就是上面的计算dp[2]得到10才是正确的44                 这种策略正确的原因就在于，完全背包问题实质上的转移方程是：45                 f[i][j]=max(f[i-1][j],f[i][j-c[i]]+w[i])--也分为两种策略 不放、放，但是放的话可以放无限件46                 细细体会吧...47             更多背包问题的资料，请参考《背包九讲》...48         */49         for(int i=1;i<=n;i++)50         {51             for(int j=v;j>=c[i];j--)52             {53                 f[j]=mmax(f[j],f[j-c[i]]+w[i]);54             }55         }56         printf("%d\n", f[v]);57     }58     return 0;59 }

 1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 int n,ans,a[201],dp[201]; 5 inline void Max(int &a,const int b){if(b>a) a=b;} 6 int main() 7 { 8     int T; 9     scanf("%d",&T);10     while(T--){11         scanf("%d",&n);12         memset(dp,0,sizeof dp);13         for(int i=0;i<n;i++) scanf("%d",a+i);14         ans=0;15         for(int k=n-1;k>=0;k--){16             int x=a[k],mx=0;17             for(int i=0;i<=k;i++){18                 if(a[i]<x) Max(mx,dp[i]);19                 else if(a[i]==x) dp[i]=mx+1;20                 if(i<k) Max(ans,dp[i]*2);21                 else Max(ans,dp[i]*2-1);22             }23         }24         printf("%d\n",ans);25     }26     return 0;27 }