区间DP（hdu5900）

题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=5900

大意：There are N pairs of numbers，Each pair consists of a key and a value，Now you need to move out some of the pairs to get the score.You can move out two continuous pairs，if and only if their keys are non coprime(their gcd is not one).The final score you get is the sum of all pair’s value which be moved out. May I ask how many points you can get the most？

N<=300，可用O（n³）算法过，显然是区间dp。

以区间dp分析，dp[i][j]来自dp[i][k]+dp[k+1][j]转移，还有就是来自本区间（因为本区间在前面是没有计算过的）（如在本题中先中间的消去，然后i与j消去）。

所以在本题中，只要判断并计算一下本区间的，然后再考虑转移就行了。

这里判断某区间能否消去，可以用前缀和，虽然我用了麻烦的方法先预处理了区间能否消去。

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<queue>
 4 #include<string.h>
 5 using namespace std;
 6 typedef long long ll;
 7 
 8 struct Node{
 9     ll k,v;
10 }node[305];
11 int cos1[305][305]={0}; //能否消去 
12 ll dp2[305][305];
13 ll gcd(ll x,ll y)
14 {    if(y==0) return x;
15     return gcd(y,x%y);
16 }
17 int main()
18 {    int T;
19     scanf("%d",&T);
20     while(T--)
21     {    int n;
22         scanf("%d",&n);
23         memset(cos1,0,sizeof(cos1));
24        
25         memset(dp2,0,sizeof(dp2));
26         for(int i=1;i<=n;i++)
27             scanf("%lld",&node[i].k);
28         for(int i=1;i<=n;i++)
29             scanf("%lld",&node[i].v);
30         for(int j=2;j<=n;j++)
31         for(int i=j-1;i>=1;i--)
32         {
33             if((j-i)%2==0) continue;
34             if((j-i)==1)
35             {
36                 if(gcd(node[i].k,node[j].k)!=1) cos1[i][j]=1;
37             } 
38             else
39             {    if(cos1[i+1][j-1]==1&&gcd(node[i].k,node[j].k)!=1) cos1[i][j]=1;
40                 else
41                 {    int k;
42                     for(k=1;i+k+1<j;k++)
43                     if(cos1[i][i+k]==1&&cos1[i+k+1][j]==1) break;
44                     if(i+k+1<j)    cos1[i][j]=1;
45                 }
46                 
47             }
48             
49         }
50         
51     for (int l = 2; l <= n; ++l) 
52     {
53     for (int i = 1, j; i <= n - l + 1; ++i) 
54         {    j = i + l - 1;
55             if(gcd(node[i].k,node[j].k)!=1) 
56             {
57             if((j-i)==1) dp2[i][j]=node[i].v+node[j].v;
58             if((j-i)>1&&cos1[i+1][j-1]==1) dp2[i][j]=node[i].v+node[j].v+dp2[i+1][j-1];
59             }
60             else  dp2[i][j]=0;
61        
62         for (int k = i; k < j; ++k) {
63            dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+1][j]);
64         }
65         
66         }
67     }
68 
69         printf("%lld
",dp2[1][n]);
70     }
71     return 0;
72  
73 }

其实代码中两个循环是一个意思，都是枚举所有区间，但要保证在计算某个区间前它的子区间都已计算过。

开始分析区间dp问题的时候我觉得采用普通dp一样的分析，假设多一单位长度，分析多的这一单位长度的影响，还有子区间都已计算好。。。。