DP训练-白红宇

DP训练

阅读量：5076 次

发布时间：2019-06-12

本文共 9959 字，大约阅读时间需要 33 分钟。

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

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

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

注意边界

1 #include
      
        2 #include
       
         3 #include
        
          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
         
          =1; i--)40             {41                 sum+=a[i];42                 if(sum==mx)43                 {44                     st=i;45                 }46             }47             printf("Case %d:\n%d %d %d\n",c,mx,st,en);48             if(c!=T)printf("\n");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
      
        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
       
        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\n",mx);30     }31     return 0;32 }

View Code

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

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

1 #include
      
        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\n",dp[bx][by]);39     }40     return 0;41 }

View Code

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

1 #include
      
        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
       
        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\n",0,a[0],a[n-1]);36         else37         printf("%d %d %d\n",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
      
        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\n",dp[0][5]);28     }29     return 0;30 }

View Code

6. POJ 1458 最长公共子序列

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

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           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

View Code

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           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                 else25                 {26                     dp[i1][j1]=max(dp[i1-1][j1],dp[i1][j1-1]);27                 }28             }29         }30         printf("%d\n",dp[i][j]);31     }32     return 0;33 }

View Code

7. VIJOS 最大递增序列数

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            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
           
            >s[i];24 memset(dp,0,sizeof(dp));25 26 for(int i=0; i

View Code

8. VIJOS 左向右递增，右向左递增*

1 #include
      
        2 #include
       
         3 #include
        
          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
         
          >a[i];15     for(int i=0; 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

View Code

9. VIJOS 最长公共子序列

1 #include
      
        2 #include
       
         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

View Code

10. VIJOS 最长递增公共子序列**

1 #include
      
        2 #include
       
         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]

View Code

11. VIJOS 最长递增子序列（包含特定项）***

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #define Maxn 3200000 7 using namespace std; 8 vector
           
            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
            
             =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 else29 {30 vector
             
              ::iterator it=lower_bound(v.begin(),v.end(),save[i]);31 *it=save[i];32 }33 }34 printf("%d\n",(int)v.size());35 return 0;36 }

View Code

12. VIJOS 递减最大价值和

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 #define INF 0x7fffffff 8 #define MAX 3002 9 #define LL long long10 struct P11 {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
           
            >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<
            
             <