Pla(jdoj1006)

　　　　题目大意：给你n个矩形，并排放在一起，你的目的是将所有的矩形全部染色。你每次染的形状为一个矩形，问：最少需要染多少次？

　　　　注释：n<=10^6，wi , hi<=2^31-1，其中，wi和hi分别是矩形的宽和高。

　　　　　　想法：第一想法是贪心，显然是不对的。在此，我们介绍一种数据结构——单调栈。顾名思义，就是维护栈里的元素是单调的。那么，在本题中，我们维护一个单调栈，每次加入一个数，判断栈顶，如果栈顶大于该数，则弹出，贡献+1，如果小于等于该数，则将该数压如栈内。最后，统计栈内元素个数，相同高度视为一种元素，贡献+=元素个数。

　　　　　　下面，我们证明，为什么这玩意儿是对的。

　　　　　　首先，先观察每次操作。如果压入的元素小于栈顶，我们设栈顶元素为h，除栈顶外的第一个元素的高度是 h - a ，想压入的元素的高度为 h - b ，那么，无论如何，栈顶高度的 min ( a , b ) 必须需要一次单独的染色。所以，这时，对于答案的贡献+1。然后，将栈顶元素的 a 染色，此时，剩余的高度与除栈顶外的第一个元素的高度是相同的，我们将它们视为一个元素，即——弹出。以此类推...最后，我们在栈中剩下的元素都是不相同的，这样，必须在需要元素个数次染色。

　　　　　　最后，附上丑陋的代码......

 #include <iostream>

 #include <cstdio>

 using namespace std;

 int a[];

 int top=;

 int main()

 {

     int n;

     int w,h;//宽与高，显然发现，宽在本题中是没有地位的

     scanf("%d",&n);

     int ans=;

     for(int i=;i<=n;i++)

     {

         scanf("%d%d",&w,&h);

         a[++top]=h;//存高

         while()//将元素压入栈中，并执行我们已经证明过的操作。

         {

             if(a[top]>a[top-]) break;

             else if(a[top]-a[top-]==)//在相等时，我们只需把栈顶元素弹出即可

             {

                 top--;

             }

             else

             {

                 top--;

                 a[top]=h;

                 ans++;

             }

         }

     }

     printf("%d",ans+top);//统计栈内剩余元素个数，即可

     return ;

 }

　　　　　　小结：错误

　　　　　　　　　　1.没有判断相等，但不至于爆蛋。

　　　　　　　　　　2.一直在裸贪心，不会转换想法。

　　　　　　　　　　3.这与NOIP の某道T1类似，但是那道题被我dp驶过，不赘述。

　　　　转载请注明：http://www.cnblogs.com/ShuraK/p/7853155.html

巴特西

Pla

Pla(jdoj1006)

最新文章

热门文章