BZOJ4380 POI2015 Myjnie

Description
n軒の洗車店が左から右に並んでいて、どの店にも正の整数価格p[i]があります.
m人が消費し、i人目はa[i]番目からb[i]番目の洗車店まで行き、これらの店の中で最も安いものを選んで消費します.しかし、この最も安い価格がc[i]より大きい場合、この人は車を洗わない.
すべての人が使うお金の合計が最大になるように、店ごとに価格を指定してください.
Input
第1行は2つの正の整数n,m(1≦n≦50,1≦m≦4000)を含む.
次にm行、各行は3つの正の整数a[i],b[i],c[i](1≦a[i]≦b[i]≦n、1≦c[i]≦5を含む×105)
Output
最初の行は、消費総額の最大値である正の整数を出力します.
2行目はn個の正の整数を出力し、各洗車店の価格p[i]を順次表し、1<=p[i]<=500000を要求する.
複数組の最適解があれば,いずれかの組を出力する.
Sample Input
7 5 1 4 7 3 7 13 5 6 20 6 7 1 1 2 5
Sample Output
43 5 5 13 13 20 20 13
Solution:
玄学三次元dp,膜Claris大
案の出力を考えないように注意します.事実は、まず案を考えると、貪欲な爆捜などの奇妙な考えを思い浮かべることを証明している.
現在の質問区間ではvali={min[L,R]0 min[L,R]≦Limitimin[L,R]>Limitiに寄与する.
思考対象が区間であればあまり考えられないような気がしますが、洗車店ごとに答えへの貢献を考えてみましょう.どんな場合、現在の洗車店でどの車が消費されるのでしょうか.

ある区域内では、現在この洗車店が最小値であり、当該区域内でかつ当該洗車店を通過する車両がここで消費される.

そこで我々は上記の内容に従ってdpを行えばよいが、dp[L][R][k]を定義することは、区間[L,R]内において、当該区間の最小値がkである場合、全行程が[L,R]内にある自動車の最適総寄与を表す.その後、どの洗車店の価格をkとし、区間が現在の洗車店を通過するかを列挙し、Limiti≧kの車両総数をh[i][k]と記す.そこで転移方程式を得た(明らかにこのkは離散する必要があり、対応する配列は私のコードにres[k]と記載されている):
dp[L][R][k]=max{dp[L][p−1][k]+dp[p+1][R][k]+res[k]×h[p][k]dp[L][R][w]p∈[L,R]w∈[k,m]
これで最適解が得られ、次の印刷スキームでは、どの洗車店から移転するか、その時点で洗車店の最適価格を格納します(dpの定義については現在列挙されている消費値が最適解であることは確定していないので......).二叉木のように区間を二つの部分に分割して再帰処理すればいいです.私の世代コードに対応するのはそれぞれf配列とv配列です.
最後の総複雑度はO(n 3 m)(やはりデータ範囲が狭いのは良いことではないが…).
Clarisさんの短い問題を補充していると思ってください.

#include 
#include 
#include 
#define N 55
#define M 4005
template <class temp>
inline bool check_max(temp &a,temp b){
    if(a>=b)return false;
    a=b;return true;
}
int dp[N][N][M],v[N][N][M],f[N][N][M],h[N][M];
int a[M],b[M],c[M],res[M];
int ans[M];
void dfs(int l,int r,int col){
    if(l>r)return;
    int mid=f[l][r][col];
    ans[mid]=v[l][r][col];
    col=v[l][r][col];
    dfs(l,mid-1,col),dfs(mid+1,r,col);
}
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&a[i],&b[i],&c[i]);
        res[i]=c[i];
    }
    std::sort(res+1,res+m+1);
    for(int i=1;i<=m;i++)
        c[i]=std::lower_bound(res+1,res+m+1,c[i])-res;
    for(int t=1;t<=n;t++)
        for(int l=1;l+t-1<=n;l++){
            int r=l+t-1;

            for(int i=l-1;i<=r;i++)
                for(int j=1;j<=m;j++)h[i][j]=0;
            for(int i=1;i<=m;i++)
                if(l<=a[i]&&b[i]<=r)
                    h[a[i]][c[i]]++,h[b[i]+1][c[i]]--;
            for(int j=1;j<=m;j++)
                for(int i=l;i<=r;i++)h[i][j]+=h[i-1][j];
            for(int i=l;i<=r;i++)
                for(int j=m;j>=1;j--)h[i][j]+=h[i][j+1];

            for(int k=m;k>=1;k--){
                f[l][r][k]=l,v[l][r][k]=k;
                for(int i=l;i<=r;i++)
                    if(check_max(dp[l][r][k],dp[l][i-1][k]+dp[i+1][r][k]+res[k]*h[i][k]))
                        f[l][r][k]=i,v[l][r][k]=k;
            }

            for(int k=m-1;k>=1;k--)
                if(check_max(dp[l][r][k],dp[l][r][k+1]))
                    f[l][r][k]=f[l][r][k+1],v[l][r][k]=v[l][r][k+1];
        }
    printf("%d
",dp[1][n][1]);

    dfs(1,n,1);
    printf("%d",(!ans[1])?res[m]:res[ans[1]]);
    for(int i=2;i<=n;i++)
        printf(" %d",(!ans[i])?res[m]:res[ans[i]]);
    putchar('
');
}