BZOJ 1200 木梳

Description

Input

第一行为整数L，其中4≤L≤100000，且有50%的数据满足L≤10⁴，表示木板下侧直线段的长。第二行为L个正整数A₁,A₂,…,A_L，其中A_i≤10⁸

Output

仅包含一个整数D，表示为使梳子面积最大，需要从木板上挖掉的格子数。

Sample Input

9
4 4 6 5 4 2 3 3 5

Sample Output

3

HINT

初看此题，这不是一道很水很水的dp题吗，一看数据范围马上枪毙。然后就放肆想，思考一下午未果，打了一发卡决策的dp，50分果断wa。最后还是研究题解去了。

贪心我看了很久，还是不会证明，理性的想想算了——对于某个木板的最优决策，一定存在|i-j|<=1，|b[i]-a[j]|<=2(其中b[i]指剪断后的木板高，a[i]指原木板高)。假设他是对的，那么我们dp的复杂度就会降到O(kL)，其中k是一个很小的常数。

我把证明发到这里(提取码：055a)，如果你看懂，我也欢迎你跟我讨论一下。

代码可能与网上其他题解的雷同，很正常，因为我是copy懂的。

 #include<cstring>
 #include<algorithm>
 #include<cstdio>
 #include<cstdlib>
 using namespace std;

 #define inf (1LL<<60)
 #define maxn 100010
 typedef long long ll;
 int h[maxn],pp[maxn][],n; ll f[maxn][][],ans=inf,sum;

 int main()
 {
     freopen("1200.in","r",stdin);
     freopen("1200.out","w",stdout);
     scanf("%d",&n);
     for (int i = ;i <= n;++i)
     {
         scanf("%d",h+i); sum += h[i];
         for (int j = h[i] - ;j <= h[i] + ;++j)
         {
             pp[i][++pp[i][]] = j;
             if (i-) pp[i-][++pp[i-][]] = j;
             if (i-) pp[i-][++pp[i-][]] = j;
             if (i +  <= n) pp[i+][++pp[i+][]] = j;
             if (i +  <= n) pp[i+][++pp[i+][]] = j;
         }
     }
     for (int i = ;i <= n;++i)
     {
         sort(pp[i]+,pp[i]+pp[i][]+);
         pp[i][] = unique(pp[i]+,pp[i]+pp[i][]+)-pp[i]-;
         while (pp[i][] && pp[i][pp[i][]] > h[i]) --pp[i][];
     }
     memset(f,,sizeof(f));
     for (int i = ;i <= pp[][];++i) f[][][i] = f[][][i] = pp[][i];
     for (int i = ;i <= n;++i)
         for (int j = ;j <= pp[i-][];++j)
             for (int k = ;k <= pp[i][];++k)
             {
                 if (pp[i-][j]<pp[i][k])
                     f[i][][k] = max(f[i][][k],f[i-][][j]+pp[i][k]);
                 else if (pp[i-][j]>pp[i][k])
                     f[i][][k] = max(f[i][][k],f[i-][][j]+pp[i][k]);
                 else
                 {
                     f[i][][k] = max(f[i][][k],f[i-][][j]+pp[i][k]);
                     f[i][][k] = max(f[i][][k],f[i-][][j]+pp[i][k]);
                 }
             }
     ans = 1LL<<;
     for (int p = ;p < ;++p)
         for (int j = ;j <= pp[n][];++j)
             ans = min(ans,sum-f[n][p][j]);
     printf("%lld",ans);
     fclose(stdin); fclose(stdout);
     return ;
 }