Hatena::Grouptopcoder

chokudaiの日記

 | 

2010-09-26

SRM 483 Div1 Medium Bribes

15:31 | SRM 483 Div1 Medium Bribes - chokudaiの日記 を含むブックマーク はてなブックマーク - SRM 483 Div1 Medium Bribes - chokudaiの日記 SRM 483 Div1 Medium Bribes - chokudaiの日記 のブックマークコメント

問題

省略

回答

前後8人しか影響を与えないので、bitDPで頑張る

public class Bribes
{
    const int mask = (1 << 8) - 1;
    const int mask2 = (1 << 9) - 1;
    const int MAX = 9999;

    public int minBribes(int[] influence, int[] resistance)
    {
        int[,] dp = new int[1 << 8, 1 << 9];
        int i, j, k, l;
        int len = resistance.Length;
        
        for (l = 0; l < len; l++)
        {
            int[] first = new int[1 << 8];
            int[] second = new int[1 << 9];
            int[,] nextdp = new int[1 << 8, 1 << 9];

            for (i = 0; i <= mask2; i++)
                for (j = 0; j < 9; j++)
                    if ((i & (1 << j)) != 0)
                    {
                        if (i <= mask)
                        {
                            if (l - j - 1 < 0) first[i] = -1;
                            else first[i] += influence[l - j - 1] / (1 << (j + 1));
                        }
                        if (l + j >= len) second[i] = -1;
                        else second[i] += influence[l + j] / (1 << (j));
                    }
            for (i = 0; i <= mask; i++)
                for (j = 0; j <= mask2; j++)
                    nextdp[i, j] = MAX;

            for (i = 0; i <= mask; i++)
            {
                if (first[i] < 0) continue;
                for (j = 0; j <= mask2; j++)
                {
                    if (second[j] < 0) continue;
                    if (dp[i, j] == MAX) continue;

                    if (first[i] + second[j] >= resistance[l])
                    {
                        int nexti = ((i << 1) + j % 2) & mask;
                        int nextj = (j >> 1);
                        nextdp[nexti, nextj + (1 << 8)]
                            = Math.Min(nextdp[nexti, nextj + (1 << 8)], dp[i, j] + j % 2);
                        nextdp[nexti, nextj]
                            = Math.Min(nextdp[nexti, nextj], dp[i, j] + j % 2);
                    }
                }
            }
            dp = (int[,])nextdp.Clone();
        }
        int res = MAX;
        for (i = 0; i <= mask; i++) res = Math.Min(res, dp[i, 0]);
        if (res == MAX) return -1;
        else return res;

    }
}
 |