Java实现 蓝桥杯VIP 算法提高 种树
2024-08-29 22:29:30
算法提高 种树
时间限制:1.0s 内存限制:256.0MB
种树
问题描述
A城市有一个巨大的圆形广场,为了绿化环境和净化空气,市政府决定沿圆形广场外圈种一圈树。园林部门 得到指令后,初步规划出n个种树的位置,顺时针编号1到n。并且每个位置都有一个美观度Ai,如果在这里种树就可以得到这Ai的美观度。但由于A城市土壤 肥力欠佳,两棵树决不能种在相邻的位置(i号位置和i+1号位置叫相邻位置。值得注意的是1号和n号也算相邻位置!)。
最终市政府给园林部门提供了m棵树苗并要求全部种上,请你帮忙设计种树方案使得美观度总和最大。如果无法将m棵树苗全部种上,给出无解信息。
输入格式
输入的第一行包含两个正整数n、m。
第二行n个整数Ai。
输出格式
输出一个整数,表示最佳植树方案可以得到的美观度。如果无解输出“Error!”,不包含引号。
样例输入
7 3
1 2 3 4 5 6 7
样例输出
15
样例输入
7 4
1 2 3 4 5 6 7
样例输出
Error!
数据规模和约定
对于全部数据,满足1<=m<=n<=30;
其中90%的数据满足m<=n<=20
-1000<=Ai<=1000
import java.util.Scanner;
public class 种树 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
int n,m,a[],i,j,dp[][][][],num;
n=Integer.parseInt(sc.next());
m=Integer.parseInt(sc.next());
num=m+1;
if(m>n/2)System.out.println("Error!");
else
{
a=new int[n];
for(i=0;i<n;i++)a[i]=Integer.parseInt(sc.next());
dp=new int[n][2][2][num];
dp[0][1][0][1]=a[0];
dp[0][0][1][1]=a[0];
for(i=1;i<n;i++)
{
for(j=1;j<num;j++)
{
dp[i][0][0][j]=Integer.MIN_VALUE/2;
dp[i][1][0][j]=Integer.MIN_VALUE/2;
dp[i][0][1][j]=Integer.MIN_VALUE/2;
dp[i][1][1][j]=Integer.MIN_VALUE/2;
}
}
if(n>1)
{
dp[1][0][1][1]=a[1];
dp[1][1][0][1]=a[0];
}
if(n>2)
{
dp[2][1][0][1]=a[0];
dp[2][0][1][1]=a[2];
if(m>2)dp[2][1][1][2]=a[0]+a[2];
dp[2][0][0][1]=a[1];
}
for(i=3;i<n;i++)
{
for(j=0;j<num;j++)
{
dp[i][0][0][j]=max(dp[i-1][0][0][j],dp[i-1][0][1][j]);
dp[i][1][0][j]=max(dp[i-1][1][0][j],dp[i-1][1][1][j]);
if(j>1&&j*2<=i+1)dp[i][0][1][j]=dp[i-1][0][0][j-1]+a[i];
else if(j==1)dp[i][0][1][j]=a[i];
if(j>1)dp[i][1][1][j]=dp[i-1][1][0][j-1]+a[i];
}
}
System.out.println(max(dp[n-1][0][0][m], max(dp[n-1][0][1][m], dp[n-1][1][0][m])));
}
}
private static int max(int i, int j) {
// TODO Auto-generated method stub
if(i>j)return i;
else return j;
}
}
最新文章
- 从css3书写顺序引出来的border-radius参数
- c#socket编程基础
- React-Native运行知乎日报遇到的问题
- Luncence .Net 使用
- Android性能优化之运算篇
- 【转】iOS-Core-Animation-Advanced-Techniques(六)
- Arcgis server - &#39; packaging failed &#39;
- jQuery插件开发 格式与解析2
- mina教程
- SuperMapPy 批量拼接 GeoTiff影像
- Bootstrap 3 与 Foundation 5
- 【刷题】【LeetCode】007-整数反转-easy
- CKEditor的使用,并实现图片上传
- Vladik and cards CodeForces - 743E (状压)
- Tensorflow 相关概念
- 调试解决iOS内存泄漏
- memcache+php实现页面访问的加速
- 「日常训练」Magic Stones(CodeForces-1110E)
- Java——Iterate through a HashMap
- (转)浅谈千万级PV/IP规模高性能高并发网站架构
热门文章
- Codeforces Round #635C Linova and Kingdom 思维
- [hdu4585]离线,并查集
- 错误提示 Table &#39;.***_ecms_news_data_&#39; doesn&#39;t exist select keyid,dokey,newstempid,closepl,info
- DNS注入以获取WebShell -asp_POST_DNS_SQLServer_GetWebShell
- 使用plupload实现多文件上传,自定义参数
- 我的linux学习日记day3
- filebeat-kafka:WARN producer/broker/0 maximum request accumulated, waiting for space
- 关于字符串函数size()的问题
- 6.1Go方法
- MySQL 5.7 基于GTID创建运行主库的从库-xtrabackup+mysqldump