题目链接:传送门
题目大意:长度为n的key数组与value数组,若相邻的key互斥,则可以删去这两个数同时获得对应的两
个value值,问最多能获得多少
题目思路:区间DP
闲谈: 这个题一开始没有做出来,找了下原因,是自己思维太局限(刷题太少),始终想怎样去维护相
邻这个条件,删去数之后怎么来拼接左右两段。。。最后导致没解出来。。
正解: 其实维护拼接我们可以用一个数组来实现,先预处理原数组中相邻的两个数,然后再利用区间
DP思想来进行扩展,最后根据这个预处理好的数组来实现判断与更新。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <stack>
#include <cctype>
#include <queue>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <climits>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define fi first
#define se second
#define ping(x,y) ((x-y)*(x-y))
#define mst(x,y) memset(x,y,sizeof(x))
#define mcp(x,y) memcpy(x,y,sizeof(y))
using namespace std;
#define gamma 0.5772156649015328606065120
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define N 1000050
#define maxn 3001
typedef pair<int,int> PII;
typedef long long LL;int n,m;
int key[],va[];
LL sum[];
int ok[][];
LL dp[][];
LL ans;
LL read(){
LL x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
}
void init(){
mst(ok,);
for(int i=;i<=n;++i)ok[i-][i]=__gcd(key[i],key[i-])==?:;
for(int l=;l<=n;++l)
for(int i=;i+l-<=n;++i){
int j=i+l-;
ok[i][j]=(ok[i+][j-]&&__gcd(key[i],key[j])!=);
for(int k=i;k<j;++k)
ok[i][j]+=(ok[i][k]&&ok[k+][j]);
}
}
void solve(){
mst(dp,);
for(int l=;l<=n;++l)
for(int i=;i+l-<=n;++i){
int j=i+l-;
if(ok[i][j]) dp[i][j]=sum[j]-sum[i-];
else{
for(int k=i;k<j;++k){
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+][j]);
}
}
}
printf("%lld\n",dp[][n]);
}
int main(){
int i,j,group;
group=read();
while(group--){
scanf("%d",&n);
for(i=;i<=n;++i) key[i]=read();
for(j=;j<=n;++j) va[j]=read(),sum[j]=sum[j-]+va[j];
init();
solve();
}
return ;
}