Fence

Fence

分析：

1. 暴力dp：

   1. 设f [ i ] [ j ] 为安排前 i 个工匠刷前 j 块木板
   2. 如果第 i 个什么也不做，
   3. 如果第 j 块木板可以空着不刷，
   4. 反之，枚举合法区间

      for (int i=1;i<=n;i++)
      {
       for (int j=1;j<=m;j++)
           f[i][j]=max(f[i][j-1],f[i-1][j]);
       for (int j=s[i];j<s[i]+len[i];j++)//枚举终点
           for (int k=j-len[i];k<s[i];k++)//枚举起点
               if(k>=0)
                   f[i][j]=max(f[i][j],f[i-1][k]+(j-k)*p[i]);
      }

2. 优化：

   1. 先改写一下式子:
   2. 当k在增大时,上界s [ i ] - 1 是不会改变的，但是下界会不断增大。如果我们对比两个决策k1,k2,假设后者位置更靠后，那么k1就会比k2更早排除出候选集合，而如果还满足
      
      那可以排除k1了。所以维护一个决策k1单调递增(优先队列)，每次在相应的范围内求出最大值

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>

using namespace std;

const int N=2e4+10,M=110;

int n,m;
int len[N],s[N],p[N],f[M][N],q[N];

struct nkl
{
    int x,y,z;
}o[M];

inline bool god(nkl xx,nkl yy)
{
    return xx.z<yy.z;
}

inline int calc(int i,int k)
{
    return f[i-1][k]-p[i]*k;
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(f,0,sizeof(f));

        for (int i=1;i<=m;i++)
        {
            scanf("%d",&o[i].x);
            scanf("%d",&o[i].y);
            scanf("%d",&o[i].z);
        }sort(o+1,o+m+1,god);
        for (int i=1;i<=m;i++)
        {
            len[i]=o[i].x;
            p[i]=o[i].y;
            s[i]=o[i].z;
        }

        for (int i=1;i<=m;i++)
        {
            int h=1,t=0;
            for (int k=max(0,s[i]-len[i]);k<s[i];k++)
            {
                while(h<=t&&calc(i,q[t])<=calc(i,k)) t--;
                q[++t]=k;
            }
            for (int j=1;j<=n;j++)
            {
                f[i][j]=max(f[i][j-1],f[i-1][j]);
                if(j>=s[i])
                {
                    while(h<=t&&q[h]<j-len[i]) h++;
                    if(h<=t) f[i][j]=max(f[i][j],calc(i,q[h])+p[i]*j);
                }
            }
        }

        printf("%d\n",f[m][n]);
    }

    return 0;
}