洛谷P8646题解 当前速读

题目描述：

(资料图片)

给定 n 个非负整数 a[1],a[2],…,a[n]，你需要选出若干个数使得它们的和最大，同时满足相邻的两个数不能同时被选中。

解题思路：

这是一道比较经典的动态规划问题，可以使用类似于背包问题的思路进行解决。具体来说，我们设 f[i] 表示前 i 个数中的最大值，且第 i 个数必须被选中的情况下的最大和，g[i] 表示前 i 个数中的最大值，且第 i 个数没有被选中的情况下的最大和。则有以下状态转移方程：

f[i]=g[i-1]+a[i]

g[i]=max(g[i-1],f[i-1]

其中 f[i] 表示第 i 个数被选中的情况，而 g[i] 表示第 i 个数不被选中的情况。最终所求答案即为 max(f[n],g[n])。

代码：

#include <bits/stdc++.h>

using namespace std;

int n,A[105];

bool dp[10005];

void init()

{

dp[0]=true; 

for(int i=1;i<=n;i++)

for(int j=0;j+A[i]<=10000;j++)

if(dp[j]) dp[j+A[i]]=true;//动态规划 

}

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++)

scanf("%d",&A[i]);

int GCD=A[1];

for(int i=2;i<=n;i++)

GCD=__gcd(GCD,A[i]);//求出最大公因数 

if(GCD>1)//特判 

{

cout<<"INF"; 

return 0;

}

init();

int ans=0;

for(int i=1;i<=10000;i++)

if(!dp[i]) ans++;//动态规划 

printf("%d",ans);

return 0;

}

关键词：