海洋之心


私信TA

用户名:wanggongsheng

访问量:122491

签 名:

等  级
排  名 17
经  验 20493
参赛次数 3
文章发表 163
年  龄 26
在职情况 学生
学  校
专  业 计算机技术

  自我简介:

读研ing,平时不登录dotcpp

解题思路:

n个位置最多种植n/2棵树,n可奇可偶
    如果位置1一定需要种植一棵树,那么位置2,n一定不可以种植树,
那么需要在3-(n-1)的位置种植m-1棵树.
因为此时最大价值=dp[n-1][m-1]+A[1]

    如果位置1不种树,那么2-n的位置都可以种植树木

因为此时最大值为dp[n][m] 

    最后从两者取最优方案

    res1 = dp1[n-1][m-1]+A[1];
	res2 = dp2[n][m];
	res = max(res1,res2);

注意事项:

    边界处理需要细心一点

参考代码:

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 31,MIN=-0x3FFFFFFF;
int dp1[N][N],dp2[N][N],A[N]; 
int main(void)
{
	
	int n,m,res1,res2,res;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>A[i]; 
	//n个位置最多种植n/2棵树,n可奇可偶 
	if(m>n/2) 
	{
		cout<<"Error!";
		return 0;
	}
	
	
	for(int j=1;j<=m-1;j++) dp1[0][j]=dp1[1][j]=dp1[2][j]=MIN; 
	/*
	如果位置1一定需要种植一棵树,那么位置2,n一定不可以种植树,
	那么需要在3-(n-1)的位置种植m-1棵树.
	因为此时最大价值=dp[n-1][m-1]+A[1] 
	*/ 
	for(int i=3;i<=n-1;i++)//i=1,2,n不需要处理 
	{
		for(int j=1;j<=m-1;j++)//1位置一定确定种植一棵树,故只需要寻找m-1棵 
		{
			dp1[i][j]=max(dp1[i-2][j-1]+A[i],dp1[i-1][j]);
		}
	}

	for(int j=1;j<=m;j++) dp2[0][j]=dp2[1][j]=MIN;
	/*
	如果位置1不种树,那么2-n的位置都可以种植树木
	因为此时最大值为dp[n][m] 
	*/
	for(int i=2;i<=n;i++)//i=1不需要处理 
	{
		for(int j=1;j<=m;j++)
		{
			dp2[i][j]=max(dp2[i-2][j-1]+A[i],dp2[i-1][j]);
		}
	}
	
	res1 = dp1[n-1][m-1]+A[1];
	res2 = dp2[n][m];
	res = max(res1,res2);
	
	cout<<res;
	return 0;
}


 

0.0分

6 人评分

  评论区

#include<stdio.h>

int a[100000];
int n,m;

int MAX(int a[])
{
	int i=0,k;
	int max=0;
	for(;i<n;i++){
		if(a[i]>max) {
			max=a[i];
			k=i;
		}
	}
	return max;
}

int main()

{
	int sum=0,j;
	scanf("%d%d",&n,&m);
	if(n/2>=m) {
		for(int i=0;i<n;i++){
			scanf("%d",&a[i]);
		}
		int b[n]={0};
		
		while(1){
			
			for(j=0;j<n;j++){
				if(a[j]==MAX(a)) break;
			}
			if(j==0){
				if(b[1]==0&&b[n-1]==0){
					b[j]=1;
					sum=sum+a[j];
					a[j]=0;
					m--;
				}
			}
			if(j==n-1){
				if(b[0]==0&&b[n-2]==0){
					b[j]=1;
					sum=sum+a[j];
					a[j]=0;
					m--;
				}
			}
			if(j!=0&&j!=n-
2020-03-11 14:45:29
  • «
  • 1
  • »