UVA11683 Laser Sculpture ：关于激光切割的一个错误的做法

[ghost]

#include<bits/stdc++.h>
using namespace std;
int shuzu[10001][10001]={};
int main ()
{
    ios::sync_with_stdio(false);
    int h,l;
    while(cin>>h>>l&&h!=0&&l!=0)
    {

      for(int i=1;i<=h;i++)     //先设置方块
       for(int j=1;j<=l;j++)
         shuzu[i][j]=1;

      for(int i=1;i<=l;i++)    //切割方块
      {
        int m; cin>>m;
        for(int j=1;j<=m;j++)
          shuzu[j][i]=0;
      }

      int cnt=0;                //计数器

      for(int i=1;i<=h;i++)     //扫描计次（找不到合适的方案）
        for(int j=1;j<=l-1;j++)
       {
          if(shuzu[i][j]==1)cnt++;
          if(shuzu[i][j]==1&&shuzu[i][j+1]==1)cnt--;//这里是错的方案，我有两个方案

       }

       cout<<cnt<<endl;
    }

    return 0;
}

[ghost]

我先通过全部方块设置为1，然后切割的变成0，接着我第一个方案就是遍历每行找到1即可，然后很快发现了错误。因为连在一起的方块会多计次。 第二个方案就是通过找到左右相邻不为相同的值的时候即可，但是我很快发现，1 0 1 这样的摆放会读出2次，事实上只需要切割一次。我就没招了

[volmodaoist]

本题需要观察一下规律，每次切割的纵向宽度都是 1，观察图片(c) 凸起部分，你会发现，如果某个地方是凸起，那么凸起部分的左右两边需要不同的轮次的切割，再看凸起部分的右边部分，也即右半边的凹陷部分，我们发现需要启动开关切割的次数等于前一个高度减去凹陷之后的高度。

那么凸起部分的左半边呢？能不能用同样的方法计算？似乎也是可以的，我们把初始状态设为矩形的高度即可，这样初始状态便可以看成是一个凸起了，你可以认为我们虚设了一个凸起（也即下面图中的黑色的部分），那么此时对于原先凸起的左半边，现在可以当做新凸起（黑色部分）右半边计算了。

经过上面的分析，我们发现切割次数与凸起部分右半边的凹陷深度有关，换个表述就是，当从较高的状态转向较低的状态的时候需要启动开关切割，而且切割次数正是二者的高度差，将其转化为编码实现，当前状态记作curr，前一个状态记作prex，当从较高的状态转向较低的状态，则累积缩写切割次数。

#include "bits/stdc++.h"
#include <iomanip>
using namespace std;

int main(){

    int A,C,curr,prex,answ;
    while(cin>>A && A){
        cin>>C;
        prex = A; answ = 0;
        for(int i = 0; i<C; ++i){
            cin>>curr;
            if(curr < prex){
                answ += (prex-curr);
            }
            prex = curr;
        }
        cout<<answ<<endl;

    }
    return 0;
}

[volmodaoist]

这边有几道类似的题目：

• 接雨水
• 买卖股票的最佳时机
• Amalgamated Artichokes
• Global Raining at Bididibus