StackOverFlowみたいです・・・もう少し基礎的な所から見直した方が良いかもしれません。これ以上先に進むのも良いですが、問題に対してもう少し慎重に望まないとマズいですね
問題元:2004TCCC Online Round4 Div1 Level1
問題文:
古い歌は「やれやれ、お隣さんはごめんです」と歌っており、オーネット町の住人はこの言葉を心に刻んでいます。どの住人も両隣の住人を嫌っています。誰も、隣人より町の井戸から遠く離れて住む気がなく、そういうわけで町は井戸の周りをぐるりと囲む様に配置されるようになりました。残念な事に町の井戸は老朽化が進み、修理の必要があります。あなたは、「われわれの井戸を守れ」財団に寄付を集める為に雇われました。町の住人は誰も、int型配列donationsの額を寄付したいとおもっており、int配列は井戸を中心とした時計回りの順になっています。けれど、隣人が寄付をしていたら自分は寄付をしません。隣人は常にdonationsに連続してリストされており、donationsの先頭と末尾も隣人同士です。集める事が出来る寄付で、最も多い金額を計算して返してください。
public class Main {
boolean[] check;
int[] donate;
int ans = Integer.MIN_VALUE;
void dfs(int pos, int sum) {
if(pos >= donate.length) return;
if(check[pos]) return;
int before = (pos - 1 < 0) ? donate.length - 1 : pos - 1;
int next = (pos + 1) % donate.length;
check[before] = check[next] = true;//この人からはもらえない
for(int r = pos; r < donate.length; r++) {
sum += donate[pos];
ans = Math.max(ans, sum);
dfs(pos + r, sum);
}
}
int maxDonations(int[] donations) {
donate = donations;
check = new boolean[donate.length];
donations = null;
for(int r = 0; r < donate.length; r++) {
dfs(0, 0);
}
return(ans);
}
void doIt() {
int[][] donations = {
{10, 3, 2, 5, 7, 8},
{11, 15},
{7, 7, 7, 7, 7, 7, 7},
{1, 2, 3, 4, 5, 1, 2, 3, 4, 5},
{94, 40, 49, 65, 21, 21, 106, 80, 92, 81, 679, 4, 61, 6, 237, 12, 72, 74, 29, 95, 265, 35, 47, 1, 61, 397, 52, 72, 37, 51, 1, 81, 45, 435, 7, 36, 57, 86, 81, 72},
};
//19, 15, 21, 16
System.out.println(maxDonations(donations[0]));
}
public static void main(String[] args) {
new Main().doIt();
}
}