(Codeforces) 313D. Ilya and Roads

http://codeforces.com/contest/313/problem/D

最近好久沒po題解了XD

這題算是一題DP題。

現在假設我們知道建造L, L+1, L+2, ...... , R-1, R的費用，我就姑且叫做w[i][j]好了(到達不到的話就設成INF)，那，我們就可以列出一個簡單的dp式子： (dp[i][j]代表我選擇了i的東西，最後一個是j)

dp[i][j] = min( min(dp[i-k][1 ~ j-k]) + w[j-k+1][j] ) ，然後呢，我們可以把裡面第二個min用陣列的方法去優化。

那，我們要怎麼知道w[i][j]呢?

可以想像的是說，如果w[i-1][j]比w[i][j]小，那我們就要把w[i][j]設定成w[i+1][j]，這個就是第一個for迴圈的部分。

第二個for迴圈的意思是說：當今天某一段可以由兩個比較小的段組合起來時，就可以用那個。

#include <iostream>
#include <stdio.h>
using namespace std;

typedef long long LL;
const int MAX_N = 306;
const LL INF = 1e17 + 6;

LL w[MAX_N][MAX_N];
LL dp[MAX_N][MAX_N]; //times,last -->best //have last
LL mn[MAX_N][MAX_N];

int main () {
    int n,m,K;
    while (scanf("%d %d %d",&n,&m,&K) != EOF) {
        for (int x=0;n+1>=x;x++) {
            for (int y=0;n+1>=y;y++) {
                w[x][y] = INF;
                dp[x][y]= INF;
                mn[x][y]= INF;
                if (x==0) mn[x][y]=dp[x][y] = 0;
            }
        }
        for (int x=0;m>x;x++) {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            w[a][b] = min(w[a][b],LL(c));
        }
        for (int i=n-1;i>=0;i--) {
            //i means lenght
            for (int j=1;n>=j+i;j++) {
                w[j][j+i] = min(min(w[j][j+i+1],w[j-1][j+i]),w[j][j+i] );
            }
        }
        for (int i=1;n>=i;i++) {
            for (int j=i+1;n>=j;j++) {
                for (int k=i;j>k;k++) {
                    w[i][j] = min(w[i][j],w[i][k] + w[k+1][j]);
                }
            }
        }
//        for (int i=1;n>=i;i++) {
//            for (int j=i;n>=j;j++) {
//                cout<<"w["<<i<<"]["<<j<<"] = "<<w[i][j]<<endl;
//            }
//        }
        LL ans=INF;
        for (int i=1;n>=i;i++) {
            for (int j=i;n>=j;j++) {
                for (int k=1;n>=k;k++) {
                    if (i-k<0) break;
                    dp[i][j] = min(dp[i][j],mn[i-k][j-k] + w[j-k+1][j]);
                    if (i>=K) ans=min(ans,dp[i][j]);
                }
                mn[i][j] = min(mn[i][j-1],dp[i][j]);
            }
        }
        if (ans<INF) printf("%I64d\n",ans);
        else puts("-1");
    }
}