UVa#1336 Fixing the Great Wall(例題9-21)

この問題のダイナミックな計画部分は直感的です.
毎回2つの決定しかありません:左に行くか右に行くか.これにより、d(i,j,k)は区間[i,j]が修復され、現在は最左端(k=0)または最右端(k=1)にあることを示す状態を設計することができる.
また,c値の総和は固定的であり,決定にかかわらず最終的には同じである.したがって,状態遷移を加える必要はない.しかし、最後にそれを加えることを忘れないでください.
だからデルタだけを考えればいいのです.転送ごとの対価は,区間[i,j]以外のすべてのノードのdelta値にロボット移動に要する時間を乗じたものである.状態遷移方程式はd(i,j)=min(d(i-1,j)+cost 1,d(i,j+1)+cost 2)である.
しかし、重視すべき詳細はたくさんあります.
1、dp配列は毎回すべてゼロにすることができなくて、TLEができます.解決策はvis配列でマークすることです
2、vis配列も毎回ゼロにすることができず、TLEもできます.解決策はkaseでタグとして機能することです
3、%.0fは自動的に四捨五入します.floorで整数部分を切り取る必要があります
4、連続区間の和(deltaの和)を求め、自然に接頭辞和を使うべきである.
5、始点位置を修復すべきノードとすることができ、cとdeltaを0とする.これで最後に分類して議論する必要はありません
6、1つの構造体の配列について、データを読み取るときはscanf("%d",&s[i].x)を直接使用し、一時変数を読んで構造関数を呼び出すよりも良い.
Run Time: 0.429s

#define UVa  "LT9-21.1336.cpp"		//Fixing the Great Wall
char fileIn[30] = UVa, fileOut[30] = UVa;

#include
#include
#include
#include
#include

using namespace std;

struct Wall {
    int x;
    double c, d;
    bool operator < (const Wall& w2) const {
        return x < w2.x;
    }
};

//Global Variables. Reset upon Each Case!
const int maxn = 1000 + 10, LEFT = 0, RIGHT = 1;
const double INF = 1e30;
int n, v, sx;
Wall walls[maxn];
double pref_d[maxn];
double sumc;
double d[maxn][maxn][2];
int vis[maxn][maxn][2];
int kase = 0;
/

double cost(int l, int r, int s, int t) {
    double result = 0.0;
    double sumd = pref_d[n] - (pref_d[r] - pref_d[l] + walls[l].d);
    int dist = abs(walls[s].x - walls[t].x);
    double tm = (double)dist / (double)v;
    result = sumd*tm;
    return result;
}

double dp(int l, int r, int k) {
    if(l == 0 && r == n) return 0;
    double& ans = d[l][r][k];
    if(vis[l][r][k] == kase) return ans;
    vis[l][r][k] = kase;
    ans = INF;

    double s = (k==LEFT)?l:r;
    if(l > 0)      //go left
        ans = min(ans, dp(l-1, r, LEFT) + cost(l, r, s, l-1));
    if(r < n)      //go right
        ans = min(ans, dp(l, r+1, RIGHT) + cost(l, r, s, r+1));
    return ans;
}

int main() {
    memset(vis, 0, sizeof(vis));
    while(scanf("%d%d%d", &n, &v, &sx) == 3 && n) {
        kase ++;

        walls[0].x = sx; walls[0].c = walls[0].d = 0;
        int sindex;
        sumc = 0;
        for(int i = 1; i < n+1; i ++) {
            scanf("%d%lf%lf", &walls[i].x, &walls[i].c, &walls[i].d);
            sumc += walls[i].c;
        }
        sort(walls, walls + n + 1);
        for(int i = 0; i < n+1; i ++) {
            if(walls[i].x == sx) sindex = i;

            pref_d[i] = walls[i].d;
            if(i) pref_d[i] += pref_d[i-1];
        }

        printf("%.0f
", floor(dp(sindex, sindex, LEFT)+(double)sumc));

    }
    return 0;
}