読者です 読者をやめる 読者になる 読者になる

日々精進

新しく学んだことを書き留めていきます

TCCC 2004 Round4 Easy

ソースコード
DPの漸化式の立て方を間違えました。最初は
dp[i] = Math.Max(dp[i - 1], dp[i - 2] + donations[i]);
だと思ったんですが、2つ飛ばしても最大になる場合があるのでこれではだめですね。
最後の家から寄付をもらうケースをどう扱うかについてもわかりませんでした。
初期値が複数パターンある場合、DPを複数回やらないとだめですね。

using System;
using System.Collections.Generic;
using System.Text;
 
 
public class BadNeighbors
{
    public int maxDonations(int[] donations)
    {
        int n = donations.Length;
        int[] dp = new int[n];
 
 
        dp[0] = donations[0];
        dp[1] = donations[1];
        for (int i = 2; i < n - 1; i++)
            dp[i] = Math.Max(max(dp, i - 1), max(dp, i - 2) + donations[i]);
 
 
        int[] dp2 = new int[n];
        dp2[1] = donations[1];
        for(int i = 2;i < n;i++)
            dp2[i] = Math.Max(max(dp2, i - 1), max(dp2, i - 2) + donations[i]);
 
 
        return Math.Max(Math.Max(dp[n - 1], dp[n - 2]), Math.Max(dp2[n - 1], dp2[n - 2]));
    }
 
 
    private int max(int[] num, int idx)
    {
        int max = 0;
        for (int i = 0; i <= idx;i++ )
            max = Math.Max(max, num[i]);
        return max;
    }
}