首页 > 代码库 > HDU5900

HDU5900

2024-08-14 12:13:53   219人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=5900

就是给出两行数字，每行有若干的数，如果相邻的两个数字的最大公约数不是1 的话拟具可以把这两数删除，并且把第二行对应的数字加起来，你的任务就是让这些数字的和最大 

 

技术分享
 1 #include<stdio.h> 2 #include<iostream> 3 #include<algorithm> 4 #include<string.h> 5 using namespace std; 6 int n; 7  8 int a[310],b[310],c[310][310]; 9 long long  dp[310][310];10 void init(){11 for(int i=2;i<=n;i++){12     for(int j=i-1;j>=1;j--){13         if(i-j==1){14             if(__gcd(a[i],a[j])!=1){///要注意函数的使用方法，前面是两个——15                 dp[j][i]=max(dp[j][i],(long long)b[i]+b[j]);///dp是long long型的，b是int型的，要进行转化，不然会出错16                 c[j][i]=1;17             }18         }19         else20         {if(c[j+1][i-1]&&__gcd(a[j],a[i])!=1){21             dp[j][i]=max(dp[j][i],dp[j+1][i-1]+(long  long)b[i]+b[j]);22             c[j][i]=1;23         }24         }25          for(int k=j;k<=i;k++){26                 if(k+1>=j && k+1<=i){27                     if(dp[j][i] < dp[j][k]+dp[k+1][i]){28                         dp[j][i]=max(dp[j][i],dp[j][k]+dp[k+1][i]);29 30                         if(c[j][k] && c[k+1][i]){///证明此区间已经不能再扩展啦31                             c[j][i]=1;32                         }33 34                         else {35                             c[j][i]=0;36                         }37                     }38                 }39          }40 41     }42 }43 }44 int main()45 {46     int t;47     cin>>t;48     while(t--){49 50         cin>>n;51         memset(dp,0,sizeof(dp));///忘记初始化会犯错的52        // memset(a,0,sizeof(a));53         //memset(b,0,sizeof(b));54         memset(c,0,sizeof(c));55         for(int i=1;i<=n;i++){56             cin>>a[i];57         }58         for(int i=1;i<=n;i++){59         cin>>b[i];60     }61     init();62   long long  ans=0;63     for(int i=1;i<=n;i++){64         for(int j=1;j<=n;j++){65             ans=max(ans,dp[i][j]);66         }67     }68     cout<<ans<<endl;69 70 }71 }
View Code

 

HDU5900


联系
我们