解题思路:
注意事项:dfs
参考代码:
import java.util.Scanner;
//DFS
public class llq1{
static final int maxn=35;
static int N=0;
static int M=0;
static int val[]=new int[maxn];
static boolean isPlanted[]=new boolean [maxn];//是否已经种了树
static int ans=0;
static int tmp=0;
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
N=s.nextInt();
M=s.nextInt();
for(int i=1;i<N+1;i++) {
val[i]=s.nextInt();
}
if(M>N/2) {
System.out.println("Error!");
return;
}
dfs(1,0);
System.out.println(ans);
}
private static void dfs(int pos, int cnt) {//pos位置,cnt已经种了多少树
// TODO Auto-generated method stub
if(cnt==M) {
ans=Math.max(ans, tmp);
return;
}
for(int i=pos;i<=N;i++) {
if(check(i)) {
tmp+=val[i];
isPlanted[i]=true;
dfs(i,cnt+1);
isPlanted[i]=false;
tmp-=val[i];
}
}
}
private static boolean check(int pos) {//检查是否可以种树
// TODO Auto-generated method stub
if(pos>N||isPlanted[pos]||isPlanted[(pos+1)%N]||isPlanted[(pos-1)%N])
return false;
return true;
}
}
0.0分
0 人评分
【蟠桃记】 (C语言代码)浏览:2222 |
C二级辅导-等差数列 (C语言代码)浏览:591 |
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:1118 |
C语言程序设计教程(第三版)课后习题7.4 (C语言代码)浏览:606 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:539 |
【排队买票】 (C语言代码)浏览:900 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:658 |
2006年春浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:669 |
整除的尾数 (C语言代码)浏览:814 |
【魔板】 (C++代码)浏览:1160 |