终于做出这题了！泪流满面啊。 首先，要理解清楚题目意思。有一道线性篱笆由N个连续的木板组成。你手上有K个工人，你要叫他们给木板涂色。每个工人有3个字段：L 表示 这个工人可以涂的最大木板数目，S表示这个工人站在哪一块木板，P表示这个工人每涂一个木板可以得到的钱。要注意的是，工人i可以选择不涂任何木板，否则，他的涂色区域必须是连续的一段，并且S[i]必须包含在内。 最后还有，每块木板只能被涂一次。 理解完题目意思后，很容易联想到邮局模型。所以看看能不能用类似的方程解决。 设f（i，j）表示使用前i个工人来对前j个木板进行涂色。 由这题，学到最重要 经验就是，一定要把every细节都想清楚才开始code，不然自找麻烦。 先看看我们要计算哪些状态，也就是每一维的值域。对于i，范围应该是[0...K]，对于每个i，j的范围应该是[0....N] 马上可以看到边界条件是 当i == 0或者 j==0的时候，f（i，j）=0 然后现在假设 i 和 j 都不为0。 如果j < s[i] , 显然，这时候f（i，j） = f（i - 1，j） 如果j >= s[i]，并且 j - s[i] + 1 < L[i]。这种情况，表示的是，工人先可以从木板s[i]开始向右连续 j - s[i] + 1涂个木板，然后工人可以决定向左涂0...L[i] - （j -s[i] +1）个木板，所以，这个时候的转移方程为： （#） f（i，j） = f（i-1，j） 或者 min { f（i-1，t） + P[i] * （s[i] - （t + 1） + 1） } + P[i] *（j -（s[i] + 1） + 1） 对于某个元组（i，j，t），这个方程的含义是，先由前i-1个工人给前t个木板涂色，然后工人i给木板t+1.....木板j进行涂色。然后，t是受到 j 和 s[i] 的约束的，必须满足j - （t + 1） + 1 <= L 为什么我们要把转移发成写成那样子呢？ 想想我们编程的时候是怎么安排计算顺序的： for i = 0 to K for j = 0 to N 计算f（i，j） 当我们在最内层循环计算f（i，j）的时候，我们可以认为i是一个常数，这样的话，当我们把转移方程写成（#）那样子的话，我们就成功把j和t分开，这样子，我们就可以在不同的状态之间共享方程里相同的一部分，而且，我们可以发现，t的上下限都是不减的，于是，我们就可以使用单调队列了。 记得，写代码之前，在纸上，画个图，清清楚楚地弄明白各个量的关系，初始值，约束等等！

千万别一上来就coding，搞清楚细节先！ 看看最后一种情况，如果j >= s[i]，并且 j - s[i] + 1 > L[i]，这时候的方程是很显然的： f（i，j） = f（i-1，j）或者 f（i-1，s[i] - 1） + P[i] * L[i]

记得排序啊

 

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef pair
         
           PairII;inline int dist(int start, int end) { return end - start + 1; }template
          
           void pushElem(DQ & q, PairII p) { while (!q.empty() && q.back().second <= p.second) q.pop_back(); q.push_back(p);}struct Worker { int L, S, P;};bool cmpWorker(const Worker & a, const Worker & b) { return a.S < b.S;}deque
           
             Q;int N, K;int f[101][16001];Worker a[101];void dp() { int i, j; for (i = 0; i <= K; ++i) { int t = 0; for (j = 0; j <= N; ++j) { int & ans = f[i][j]; ans = 0; if (i == 0) { ans = 0; } else if (j == 0) { ans = 0; } else if (j < a[i].S) { ans = f[i - 1][j]; } else if (a[i].S <= j && dist(a[i].S, j) < a[i].L) { ans = f[i - 1][j]; int rest = a[i].L - dist(a[i].S, j); int left = max(0, a[i].S - rest - 1); while (t <= a[i].S - 1) { pushElem(Q, make_pair(t, f[i - 1][t] + a[i].P * dist(t + 1, a[i].S))); t += 1; } while (!Q.empty() && Q.front().first < left) Q.pop_front(); if (!Q.empty()) { ans = max(ans, Q.front().second + dist(a[i].S + 1, j) * a[i].P); } } else if (dist(a[i].S, j) >= a[i].L) { ans = max(f[i - 1][j], f[i - 1][a[i].S - 1] + a[i].L * a[i].P); } else { assert(0); } } }}void input() { scanf("%d %d", &N, &K); int i, j; for (i = 1; i <= K; ++i) { scanf("%d %d %d", &(a[i].L), &(a[i].P), &(a[i].S)); } //因为尼玛忘记排序，wa了好多次！！！ sort(a + 1, a + K + 1, cmpWorker);}int main() { input(); dp(); printf("%d\n", f[K][N]); return 0;}