AGC 004 B - Colorful Slimes - バイトの競プロメモ

N種類のスライムを最短で手に入れたい

２つの操作が行える
ai秒でスライムiを手に入れる
x秒で全てのスライムの添字を魔法で1増やす(スライムNはスライム1になる)

制約

2<=N<=2000
1<=ai<=10^9
1<=x<=10^9

解法

初めに考え違いをした。
スライムiを手に入れる最小コストはai,ai-1 + x, ai-2 + x*2 ,.... のどれかなんだから、上記の方法で全てのスライムに対して最小コストのスライムを持っておく。そして、それらを合計して、その中で最大の魔法を使った数*x秒を足せばいいと思った。

しかし、スライムを魔法で動かした時に他のスライムも動き、もっと少ない結果があるので上は間違っている。

上のことから魔法を使う回数は全体に影響があり、回数が分かっていれば、あるスライムに対して最小のコストで呼び出せるスライムが一意に決まる事が分かりたかった

問題の芯
何かしら不定の値、境目があり、それが決まれば他の値が一意に定まる場合、その値を全パターン試したい

類題
D - 3N Numbers

public static void main(String[] args)
    {
        N = sc.nextInt();
        long x = sc.nextInt();
        A = sc.nextLongArray(N);
        long[][] minc = new long[N][N];//スライムiがm回魔法を使う時の最小値ai
        for (int i = 0; i < N; i++)
        {
            minc[i][0] = A[i];
        }

        for (int i = 0; i < N; i++)
        {
            for (int m = 1; m < N; m++)
            {
                int si = i - m;
                if (si < 0) si += N;
                minc[i][m] = Math.min(minc[i][m-1], A[si]);

            }
        }
        long minRes = Long.MAX_VALUE;
        for (int m = 0; m < N; m++)
        {
            long res = 0;
            for (int i = 0; i < N; i++)
            {
                res += minc[i][m];
            }
            res += m*x;
            minRes = Math.min(minRes,res);
        }
        System.out.println(minRes);
    }