C++11(clang++ 3.9) 解法, 执行用时: 237ms, 内存消耗: 78052K, 提交时间: 2019-04-13 15:01:56

#include<bits/stdc++.h>
#define F first
#define S second
#define mk make_pair
#define pb push_back
using namespace std;
typedef pair<int,int> pii;
const int maxn = 35, maxm = 2010;
int l[maxm], r[maxm], c[maxm], d[maxm], n, m, a[maxn], ans[maxn];
pii mx[maxn][maxn][maxm*2], dp[maxn][maxn][maxm*2];
vector<int> v, vc[maxm*2], vd[maxm*2];

void get_ans(int L=1, int R=n, int val=0){
    if(L>R) return;
    int mxval = mx[L][R][val].S, pos = dp[L][R][mxval].S;
    ans[pos] = v[mxval];
    get_ans(L, pos-1, mxval); 
    get_ans(pos+1, R, mxval); 
}

// c[i]<=  <=d[i]
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d%d%d",l+i,r+i,c+i,d+i);
        v.pb(c[i]), v.pb(d[i]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for(int i=0;i<m;i++){
        c[i] = lower_bound(v.begin(),v.end(),c[i]) - v.begin();
	    d[i] = lower_bound(v.begin(),v.end(),d[i]) - v.begin();
        vc[c[i]].pb(i);
        vd[d[i]].pb(i);
    }
    int up = v.size();
    for(int L=n;L>=1;L--){
        for(int R=L;R<=n;R++){
            for(int i=L;i<=R;i++) a[i]=0;
            for(int mm=up-1;mm>=0;mm--){
                for(int i: vd[mm]) if(l[i]>=L&&r[i]<=R) a[l[i]]++, a[r[i]+1]--;
                int cnt = 0;
                for(int i=L;i<=R;i++){
                    cnt += a[i];
                    int value = mx[L][i-1][mm].F + mx[i+1][R][mm].F + cnt*v[mm];
                    if(value >= dp[L][R][mm].F) dp[L][R][mm] = mk(value, i);
                    //dp[L][R][mm] = max(dp[L][R][mm],
                    //mk(mx[L][i-1][mm].F+mx[i+1][R][mm].F+cnt*v[mm], i));
                }
                mx[L][R][mm] = max(mx[L][R][mm+1], mk(dp[L][R][mm].F, mm));
                for(int i: vc[mm]) if(l[i]>=L&&r[i]<=R) a[l[i]]--, a[r[i]+1]++;
            }
        }
    }
    get_ans();
    printf("%d\n", mx[1][n][0].F);
    for(int i=1;i<=n;i++) printf("%d%c", ans[i], " \n"[i==n]);
    return 0;
}