DP训练

1. HDU 1003 最大和连续子序列

状态方程：dp[i]=max(dp[j-1]+num[i],num[i]);

解：存放dp数组每个元素都是从左至右最大连续子序列的值，即dp[i]为从0～i处最大连续子序列的值

注意边界

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<string.h>
 4 using namespace std;
 5 #define N 100005
 6 int dp[N];
 7 int a[N];
 8 int main()
 9 {
10     int t;
11     while(scanf("%d",&t)!=EOF)
12     {
13         int c=1,T=t;
14         while(t--)
15         {
16             memset(dp,0,N);
17             int n;
18             scanf("%d",&n);
19             for(int i=1; i<=n; i++)
20             {
21                 scanf("%d",&a[i]);
22             }
23             dp[1]=a[1];
24             for(int j=2; j<=n; j++)
25             {
26                  dp[j]=max(dp[j-1]+a[j],a[j]);
27             }
28 
29             int mx=-999999999;
30             int st=0,en=0;
31             for(int i=1; i<=n; i++)
32                 if(mx<dp[i])
33                 {
34                     mx=dp[i];
35                     en=i;
36                 }
37             st=en;
38             int sum=0;
39             for(int i=en; i>=1; i--)
40             {
41                 sum+=a[i];
42                 if(sum==mx)
43                 {
44                     st=i;
45                 }
46             }
47             printf("Case %d:
%d %d %d
",c,mx,st,en);
48             if(c!=T)printf("
");
49             c+=1;
50         }
51     }
52     return 0;
53 }

View Code

2. HDU 1087 最大和连续递增子序列

状态方程：v[i]=max(v[i],v[j]+num[i]);//v[j]存放的为最优的递增和加上当前的

解：存放dp数组的每个元素都是从左至右最大和递增子序列的值，即dp[i]为0～i处最优最大和递增子序列的值

例如：五个数：5 1 2 4 6

扫描到6时，从第一开始向后扫描，5<6 v[0]=5,num[i]=6,此时v[i]=11,

　　　　　　　　　　　　　　　 1<6 v[1]=1,~~ v[i]=11

　　　　　　　　　　　　　　　 2<6 v[2]=3~~ v[i]=11

　　　　　　　　　　　　　　　　4<6 v[3]=7 ~~ v[i]=13

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 1005
 4 int num[N];
 5 int v[N];
 6 int main()
 7 {
 8     int n;
 9     while(scanf("%d",&n)!=EOF&&n)
10     {
11         memset(v,0,sizeof(v));
12         for(int i=1; i<=n; i++)
13             scanf("%d",&num[i]);
14 
15         for(int i=1; i<=n; i++)
16         {
17             for(int j=1; j<i; j++)
18             {
19                 if(num[i]>num[j])
20                     v[i]=max(v[i],v[j]+num[i]);
21             }
22             v[i]=max(v[i],num[i]);
23         }
24         int mx=-999999;
25         for(int i=1; i<=n; i++)
26         {
27             mx=max(mx,v[i]);
28         }
29         printf("%d
",mx);
30     }
31     return 0;
32 }

View Code

3. 马拦卒过河(动态规划思维)

解：每个位置为上一个与左一个路径之和

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 16
 4 int dp[N][N];
 5 
 6 void mControl(int x,int y)
 7 {
 8     int xx[8]= {x-2,x-2,x-1,x-1,x+1,x+1,x+2,x+2};
 9     int yy[8]= {y-1,y+1,y-2,y+2,y+2,y-2,y+1,y-1};
10     for(int i=0; i<8; i++)
11         if(xx[i]>=0&&yy[i]>=0&&xx[i]<=15&&yy[i]<=15)
12         {
13             dp[xx[i]][yy[i]]=-1;
14         }
15     dp[x][y]=-1;
16 }
17 int main()
18 {
19     int bx,by,mx,my;
20     while(scanf("%d%d%d%d",&bx,&by,&mx,&my)!=EOF)
21     {
22         memset(dp,0,sizeof(dp));
23         mControl(mx,my);
24         dp[0][0]=1;
25         for(int i=0; i<=bx; i++)
26         {
27             for(int j=0; j<=by; j++)
28             {
29                 if(dp[i][j]!=-1)
30                 {
31                     if(dp[i][j-1]!=-1&&j>0)
32                         dp[i][j]+=dp[i][j-1];
33                     if(dp[i-1][j]!=-1&&i>0)
34                         dp[i][j]+=dp[i-1][j];
35                 }
36             }
37         }
38         printf("%d
",dp[bx][by]);
39     }
40     return 0;
41 }

View Code

4. HDU 1231 最大和连续子序列（同1，1输出下标，本题是输出值）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int a[100005];
 4 int dp[100005];
 5 int main()
 6 {
 7 
 8     int n;
 9     while(scanf("%d",&n)!=EOF&&n)
10     {
11         for(int i=0; i<n; i++)
12             scanf("%d",&a[i]);
13         dp[0]=a[0];
14         for(int i=1; i<n; i++)
15         {
16             dp[i]=max(dp[i-1]+a[i],a[i]);
17         }
18         int mx=-9999999;
19         int st,en;
20         for(int i=0; i<n; i++)
21         {
22             if(dp[i]>mx)
23             {
24                 mx=dp[i];
25                 en=i;
26             }
27         }
28         int sum=0;
29         for(int i=en;i>=0;i--)
30         {
31             sum+=a[i];
32             if(sum==mx)
33             st=i;
34         }
35         if(mx<0)printf("%d %d %d
",0,a[0],a[n-1]);
36         else
37         printf("%d %d %d
",mx,a[st],a[en]);
38     }
39     return 0;
40 }

View Code

5.HDU 1176 免费馅饼

状态方程：

　　特判:dp[time][0]+=max(dp[time+1][0],dp[time+1][1];

　　　　dp[time][point]+=max(dp[time+1][point-1],dp[time+1][point],dp[time+1][point+1]) //这里没有特判最后一个位置（当位置为10，辉加到11这个位置），只要将数组多一位即可，该位置默认存放的是0，所以不会影响　　

解：用一个二位数组存放dp[time][point],从最后落下的时间向前扫描，每次存放的是下一秒与当前该位置能获得的最多的馅饼。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 100005
 4 #define maxx(a,b,c) (max(max(a,b),c))
 5 int dp[N][12];
 6 int main()
 7 {
 8     int n;
 9     while(scanf("%d",&n)!=EOF&&n)
10     {
11         memset(dp,0,sizeof(dp));
12         int point,time,maxT=0;
13         for(int i=1;i<=n;i++)
14         {
15             scanf("%d%d",&point,&time);
16             dp[time][point]+=1;
17             maxT=max(maxT,time);
18         }
19         for(int i=maxT-1;i>=0;i--)
20         {
21             dp[i][0]+=max(dp[i+1][0],dp[i+1][1]);
22             for(int j=1;j<=10;j++)
23             {
24                 dp[i][j]+=maxx(dp[i+1][j],dp[i+1][j+1],dp[i+1][j-1]);
25             }
26         }
27         printf("%d
",dp[0][5]);
28     }
29     return 0;
30 }

View Code

6. POJ 1458 最长公共子序列

参考链接：http://blog.csdn.net/u012102306/article/details/53184446

 1 #include<iostream>
 2 #include<string.h>
 3 #include<string>
 4 #include<algorithm>
 5 using namespace std;
 6 #define MAX 1002
 7 int dp[MAX][MAX];
 8 int main()
 9 {
10     string a,b;
11     int i,j;
12     while(cin>>a>>b){
13         memset(dp,0,sizeof(dp));
14         for(i=0;i<a.length();i++)
15             for(j=0;j<b.length();j++)
16                 if(a[i]==b[j])
17                     dp[i+1][j+1]=dp[i][j]+1;
18                 else
19                     dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
20         cout<<dp[i][j]<<endl;
21     }
22     return 0;
23 }

View Code

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<string>
 4 #include<iostream>
 5 using namespace std;
 6 #define N 10005
 7 int dp[N][N];
 8 int main()
 9 {
10     string s1,s2;
11     while(cin>>s1>>s2)
12     {
13         int i=s1.length(),j=s2.length();
14         for(int i1=0; i1<=i; i1++)
15         {
16             for(int j1=0; j1<=j; j1++)
17             {
18                 if(i1==0||j1==0)
19                     dp[i1][j1]=0;
20                 else if(s1[i1-1]==s2[j1-1])
21                 {
22                     dp[i1][j1]=dp[i1-1][j1-1]+1;
23                 }
24                 else
25                 {
26                     dp[i1][j1]=max(dp[i1-1][j1],dp[i1][j1-1]);
27                 }
28             }
29         }
30         printf("%d
",dp[i][j]);
31     }
32     return 0;
33 }

View Code

7. VIJOS 魔族密码最大递增序列数

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<string>
 4 #include<string.h>
 5 #include<iostream>
 6 using namespace std;
 7 #define N 2005
 8 int dp[N];
 9 string s[N];
10 int check(string a,string b)
11 {
12     int len=min(a.length(),b.length());
13     for(int i=0; i<len; i++)
14         if(a[i]!=b[i])return 0;
15     return 1;
16 }
17 int main()
18 {
19     int n;
20     while(scanf("%d",&n)!=EOF&&n)
21     {
22         for(int i=0; i<n; i++)
23             cin>>s[i];
24         memset(dp,0,sizeof(dp));
25 
26         for(int i=0; i<n; i++)
27         {
28             for(int j=0; j<i; j++)
29                 if(check(s[i],s[j]))
30                     dp[i]=max(dp[i],dp[j]+1);
31         }
32         int ans=-1e8;
33         for(int i=0; i<n; i++)
34             ans=max(ans,dp[i]);
35         cout<<ans+1<<endl;
36     }
37     return 0;
38 }

View Code

8. VIJOS 合唱队列左向右递增，右向左递增*

 1 #include<iostream>
 2 #include<string.h>
 3 #include<algorithm>
 4 #define MAX 105
 5 using namespace std;
 6 int a[MAX],l[MAX],r[MAX];
 7 int main()
 8 {
 9     int n;
10     cin>>n;
11     memset(l,0,sizeof(l));
12     memset(r,0,sizeof(r));
13     for(int i=0; i<n; i++)
14         cin>>a[i];
15     for(int i=0; i<n; i++)
16         for(int j=0; j<i; j++)
17             if(a[i]>a[j])
18                 l[i]=max(l[i],l[j]+1);
19 
20     for(int i=n-1; i>=0; i--)
21         for(int j=n-1; j>i; j--)
22             if(a[i]>a[j])
23                 r[i]=max(r[i],r[j]+1);
24     int ans=-1e8;
25     for(int i=0; i<n; i++)
26         ans=max(ans,r[i]+l[i]);
27     cout<<n-(ans+1)<<endl;
28     return 0;
29 }

View Code

9. VIJOS 小胖的水果最长公共子序列

 1 #include<iostream>
 2 #include<string.h>
 3 using namespace std;
 4 #define MAX 1005
 5 int dp[MAX][MAX];
 6 string a,b;
 7 int main()
 8 {
 9     while(cin>>a>>b)
10     {
11         int alen=a.length();
12         int blen=b.length();
13         for(int i=0; i<alen; i++)
14         for(int j=0; j<blen; j++)
15         {
16             if(a[i]==b[j])
17                 dp[i+1][j+1]=dp[i][j]+1;
18             else
19                 dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
20         }
21         cout<<alen+blen-dp[alen][blen]<<endl;
22     }
23     return 0;
24 }

View Code

10. VIJOS 神秘的咒语最长递增公共子序列**

 1 #include<iostream>
 2 #include<string.h>
 3 using namespace std;
 4 #define ll long long
 5 #define MAX 505
 6 ll a1[MAX],b1[MAX];
 7 int f[MAX];
 8 int main()
 9 {
10     int T;
11     cin>>T;
12     while(T--)
13     {
14         int a,b;
15         cin>>a;
16         for(int i=1; i<=a; i++)
17             cin>>a1[i];
18         cin>>b;
19         for(int i=1; i<=b; i++)
20             cin>>b1[i];
21         memset(f,0,sizeof(f));
22         int ans=0;
23         for(int i=1; i<=a; ++i)
24         {
25             int maxx=0;
26             for(int j=1; j<=b; ++j)
27             {
28                 if(b1[j]<a1[i])maxx=max(maxx,f[j]);
29                 if(b1[j]==a1[i])
30                 {
31                     f[j]=maxx+1;
32                     ans=max(ans,f[j]);
33                 }
34             }
35         }
36         cout<<ans<<endl;
37     }
38     return 0;
39 }

View Code

11. VIJOS 难解的问题最长递增子序列（包含特定项）***

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 #include <vector>
 6 #define Maxn 3200000
 7 using namespace std;
 8 vector<int>v;
 9 int save[Maxn];
10 int main()
11 {
12     int n = 0, k = 0, knum = 0;
13     scanf("%d%d",&n,&k);
14     for(int i=1; i<=n; i++)
15     {
16         scanf("%d",&save[i]);
17         if(i==k)
18             knum=save[i];
19     }
20     for(int i=1; i<=n; i++)
21     {
22         if(i<k&&save[i]>=knum)
23             continue;
24         if(i>k&&save[i]<=knum)
25             continue;
26         if(v.size()==0||save[i]>v[v.size()-1])
27             v.push_back(save[i]);
28         else
29         {
30             vector<int>::iterator it=lower_bound(v.begin(),v.end(),save[i]);
31             *it=save[i];
32         }
33     }
34     printf("%d
",(int)v.size());
35     return 0;
36 }

View Code

12. VIJOS 雷曼兔递减最大价值和

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<string.h>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 #define INF 0x7fffffff
 8 #define MAX 3002
 9 #define LL long long
10 struct P
11 {
12     int x,y,h;
13 } p[MAX];
14 int dp[MAX];
15 bool cmp(const P a,const P b)
16 {
17     return a.h<b.h;
18 }
19 int main()
20 {
21     int n;
22     cin>>n;
23     int l = 1;
24     for(int i = 1; i <= n; ++i)
25         for(int j = 1; j <= n; ++j)
26         {
27             cin>>p[l].h;
28             p[l].x=i;
29             p[l].y=j;
30             l++;
31         }
32     sort(p,p+l,cmp);
33     dp[1]=0;
34     for(int i = 2; i <= n*n; ++i)
35     {
36         int tem = 0;
37         for(int j = 1; j < i; ++j)
38         {
39             int t = abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y);
40             t *= t;
41             tem = max( tem,t+dp[j]);
42         }
43         dp[i] = tem;
44     }
45     cout<<dp[n*n]<<endl;
46     return 0;
47 }

View Code