题解：CF1517C Fillomino 2

Ratio_Y · 2024-08-12 12:08:21 · 题解

思路

倒序考虑，在第 n 行一定只能向左扩展。

类似于俄罗斯方块，这里我们被硬性要求不能留空，所以为避免出现一种数将三角形“隔断”，我们应优先在边缘区域放数。

形象一下，我们在能向下扩展时向下走，才能给上面的数“腾更多的空间”，如此便得到了最优决策，复杂度 \mathcal{O(n^2)}。

实现

#include<bits/stdc++.h>

const int Ratio=0;
const int N=505;
int n;
int a[N],dh[N][N];
namespace Wisadel
{
    short main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=n;i>=1;i--)
        {
            dh[i][i]=a[i];
            int sum=1,x=i,y=i;
            while(sum<a[i])
            {
                if(x<n&&!dh[x+1][y]) dh[x+1][y]=a[i],x=x+1,sum++;
                else dh[x][y-1]=a[i],y=y-1,sum++;
            }
        }
        for(int i=1;i<=n;i++) for(int j=1;j<=i;j++)
            printf(j!=i?"%d ":"%d\n",dh[i][j]);
        return Ratio;
    }
}
int main(){return Wisadel::main();}

完结撒花~