题目描述 Description
给出一个长度为N的序列A(A1,A2,A3,...,AN)。现选择K个互不相同的元素，要求： 1.两两元素互不相邻
2.元素值之和最大
输入描述 Input Description
第一行两个正整数N，K。 接下来一行N个整数，描述A。
输出描述 Output Description
输出一行一个整数，描述答案（最大和）。
样例输入 Sample Input
样例1：
7 3
3 5 7 -1 9 10 7
样例2：
7 3
3 21 7 -1 9 20 7
样例输出 Sample Output
样例1：
23
样例2：
40
数据范围及提示 Data Size & Hint
测试点编号 数据范围
1,2,3 K≤N≤20
4,5,6,7,8,9,10 K≤N≤1000
分类标签 Tags 点此展开
AC代码(不靠谱版)：
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e3+;
ll n,k,a[N],f[N][N];
int main(){
scanf("%lld%lld",&n,&k);
for(int i=;i<=n;i++) scanf("%lld",&a[i]);
f[][]=a[];
for(int i=;i<=n;i++){
for(int j=;j<=k;j++){
f[i][j]=max(f[i-][j],f[i-][j-]+a[i]);
}
}
printf("%lld\n",f[n][k]);
return ;
}
AC代码(靠谱版)：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e3+;
ll n,k,a[N],f[N][N][];
int main(){
memset(f,-,sizeof f);
scanf("%lld%lld",&n,&k);
for(int i=;i<=n;i++) scanf("%lld",&a[i]);
for(int i=;i<=n;i++) f[i][][]=;
for(int i=;i<=n;i++){
for(int j=;j<=k;j++){
f[i][j][]=max(f[i-][j][],f[i-][j][]);
f[i][j][]=max(f[i-][j-][]+a[i],f[i][j][]);
}
}
printf("%lld\n",max(f[n][k][],f[n][k][]));
return ;
}