zoj 1428 Magazine Delivery (DP)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1428

今天练习赛的题目，我先读的，以为是图论，叫XSY去看，结果越弄越理不清头绪。。最后没办法只能放弃。

下午结束后才知道原来是道DP。以三辆车的位置为状态，j,k为不动的车位置，i为当前移动车的位置。dp[j,k,i]可由dp[j,k,i+1],dp[j,i,i+1],dp[k,i,i+1]移动一次达到。

另外长了个记性，以后绝对不再使用宏定义了，宏定义的取最值方法老是出错，找不出来原因。

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std ;
int data[31][31] ;
int dp[31][31][31] ;
int main(){
    int t, n, i, j, k ;
    scanf("%d", &t) ;
    while(t--){
        memset(dp, 0, sizeof(dp)) ;
        scanf("%d", &n) ;
        for(i=1; i<n; i++)
            for(j=i+1; j<=n; j++)
                scanf("%d", &data[i][j]) ;
        for(i=n-1; i>=1; i--)
            for(j=1; j<=i; j++)
                for(k=1; k<=i; k++){
                    dp[j][k][i] = min(dp[j][k][i+1]+data[i][i+1], dp[k][i][i+1]+data[j][i+1]) ;
                    dp[j][k][i] = min(dp[j][k][i], dp[j][i][i+1]+data[k][i+1]) ;
                }
        printf("%d\n", dp[1][1][1]) ;
    }
    return 0 ;}