俄罗斯方块

2

俄罗斯方块，你可以一次消除一行，也可以一次消除一列。然后给你每一列的的方块个数。
解题思路：
1
2
3
4
5
6
7
8
刚开始是贪心，后面实测WA。
sort一遍，让其保持单调下降，然后从后往前进行枚举，进行动态规划。

动态转移方程如下：
ans=min(ans,a[i]+i-1);
为什么是这个呢？
大家可以画个图深入理解一下，这里就不和大家讲了。
时空复杂度
1
2
时间复杂度：O(n)
空间复杂度：O(1)
AC代码如下：

#include<bits/stdc++.h>
using namespace std;
int m,a[1000],n;
int ans;
bool cmp(int a,int b){return a>b;}//sort标配不解释
int main()
{
    scanf("%d",&m);
    while(m--)
    {
        ans=2147483647;//求最小值，所以赋初值为极大值
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }a[n+1]=0;//添加末尾0，让ans可以不漏答案
        sort(a+1,a+n+1,cmp);
        for(int i=n+1;i>=1;i--)
        ans=min(ans,a[i]+i-1);//动态转移
        printf("%d",ans);
        if(m)printf("
");//防止PE，前文讲过。
    }
    return 0;
}