SGU 183 Painting the balls

對於一個題目，可以寫出來的DP形式非常多種

最重要的是要找到一個可以使時間複雜度最低的方法

像是這題 Painting the balls

可以想成dp[i][j] 是 考慮到 i , 且放的位置為 i 和 i-j 時，最小的cost

這時就可以構造出一個O(m)的轉移過程

總time complexity為O(n^2*m)

在分析轉移過程的時候，可能會看到一些奇妙的東西

這時如果把dp[i][j] 變成 考慮到 i , 且放的位置為 i 和 i-1~ i-j 當中最小cost 

轉移式就可以變成：

dp[ i ][1] = dp[i-1][m-1] + cost[ i ]

dp[ i ][ j ] = min(dp[ i ][j-1], dp[i-j][m-j] + cost[ i ])

這樣總time complexity就壓成O(nm) 了

//By momo
#include<cstdio>
#include<algorithm>
#define INF 999999999
using namespace std;

int n, m, ans = INF, c[10010];
class mod_array{
    public:
    int dat[128][128];
    int* operator[](int x){ return dat[x & 127]; }
}opt;

int main(){
    fill((int*)opt.dat, (int*)opt.dat+127*127, INF);
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%d", &c[i]);
    for(int i = 0; i < n; i++){
        for(int j = 1; j < m && j <= i; j++){
            if(i < m) opt[i][j] = min(opt[i][j-1], c[i-j]+c[i]);
            else if(j == 1) opt[i][j] = opt[i-1][m-1] + c[i];
            else opt[i][j] = min(opt[i][j-1], opt[i-j][m-j] + c[i]);
        }
    }
    for(int i = n-m+1; i < n; i++)
        ans = min(ans, opt[i][i-n+m]);
    printf("%d\n", ans);
}

可以注意的地方是我的opt寫法，那是來自網路上某中國強者的寫法
http://hi.baidu.com/yccbolg/item/06e9351a84445cf487ad4ec9

寫成這樣之後就不用像以前在下面寫一大堆的模運算了，代碼漂亮很多