UVa 10337

the same with UVa 116 with more restrictions, and target state is  dp[9][X/100] but not dp[9][X/100-1], so...
state:
    dp[i][j] - minimum fuel used at altitude i and distance j
transition:
    dp[i][j]=min(dp[i][j], dp[p[k]][j-1]+cost) for all 0<k<3
    the restriction is resolved with setting cost of them equal to HOLD altitude's cost

/* UVas */
/*****************************************************************************/
int c, x;
int main(void) {
    cin>>c;
    while (c--) {
        cin>>x;
        int w[10][x/100];
        int d[10][x/100+1];
        for (int i=0; i<10; i++) {
            for (int j=0; j<x/100; j++) {
                cin>>w[i][j];
            }
        }
        for (int i=0; i<10; i++) {
            for (int j=0; j<=x/100; j++) {
                d[i][j]=INT_MAX;
            }
        }
        d[9][0]=0;
        for (int j=1; j<=x/100; j++) {
            for (int i=0; i<10; i++) {
                int p[3]={i==0?i:i-1, i, i==9?i:i+1};
                int c[3]={i==0?-w[i][j-1]:-w[i-1][j-1], -w[i][j-1], i==9?-w[i][j-1]:-w[i+1][j-1]};
                int C[3]={20, 30, 60};
                for (int k=0; k<3; k++) {
                    if (d[p[k]][j-1]==INT_MAX) {
                        continue;
                    }
                    int cost=C[k]+c[k];
                    d[i][j]=min(d[i][j], d[p[k]][j-1]+cost);
                }
            }
        }
        cout<<d[9][x/100]<<endl<<endl;
    }
    return 0;
}
/*****************************************************************************/