首页 > 代码库 > 4815 江哥的dp题a
4815 江哥的dp题a
4815 江哥的dp题a
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 黄金 Gold
题目描述 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代码1：
f[i][j]表示前i个元素，已选j个互不相邻的元素的最优值
（可能有bug）
#include<cstdio>#include<algorithm>#define ll long longusing namespace std;const int N=1e3+10;ll n,k,a[N],f[N][N];int main(){ scanf("%lld%lld",&n,&k); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); f[1][1]=a[1]; for(int i=2;i<=n;i++){ for(int j=1;j<=k;j++){ f[i][j]=max(f[i-1][j],f[i-2][j-1]+a[i]); } } printf("%lld\n",f[n][k]); return 0;}
AC代码2：
f[i][j][0]表示前i个元素(第i个元素不选)，已选j个互不相邻的元素的最优值
f[i][j][1]表示前i个元素(第i个元素选)，已选j个互不相邻的元素的最优值
（简单清晰的思路）
#include<cstdio>#include<cstring>#include<algorithm>#define ll long longusing namespace std;const int N=1e3+10;ll n,k,a[N],f[N][N][2];int main(){ memset(f,-63,sizeof f); scanf("%lld%lld",&n,&k); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=0;i<=n;i++) f[i][0][0]=0; for(int i=1;i<=n;i++){ for(int j=1;j<=k;j++){ f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]); f[i][j][1]=max(f[i-1][j-1][0]+a[i],f[i][j][1]); } } printf("%lld\n",max(f[n][k][0],f[n][k][1])); return 0;}
4815 江哥的dp题a
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。