社区讨论

有大佬看一看这样为什么能过吗

P1034[NOIP 2002 提高组] 矩形覆盖参与者 21已保存回复 47

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
47 条
当前快照
1 份
快照标识符
@mi6li7t1
此快照首次捕获于
2025/11/20 06:50
4 个月前
此快照最后确认于
2025/11/20 07:01
4 个月前
查看原帖
这是我们机房一个神犇的代码,不知道为啥就过了
s[i][j]据他所言是表示把i点和j点作为对角线顶点构造出矩形的面积,
但是按他的做法似乎并不是这样,他自己也弄不明白了
请各位大佬指教一下,难道这仅仅是因为数据水吗?
CPP
#include<iostream>
#include <cstdio>
#include <cstdlib>
#include<cstring>
using namespace std;
#define MAXN 60 
#define MAXINT 1000010
struct node {
    int x,y;
} a[MAXN];
int f[MAXN][5],s[MAXN][MAXN],n,m,high,low;
int cmp(const void *a,const void *b) 
{
    node c=*(node *)a,d=*(node *)b;
    if (c.x<d.x) return -1; if (c.x>d.x) return 1;
    if (c.y<d.y) return -1;if (c.y>d.y)    return 1;
    return 0;
}
int main() 
{
    scanf("%d%d",&n,&m);
    for (int i=1; i<=n; ++i)
        scanf("%d%d",&a[i].y,&a[i].x);
    qsort(a+1,n,sizeof(node),cmp);
    for (int i=1; i<=n; ++i) 
    {
        high=a[i].y,low=a[i].y;
        for (int j=i; j<=n; ++j) 
        {
            if (a[j].y>high) high=a[j].y;
            if (a[j].y<low)    low=a[j].y;
            s[i][j]=(high-low)*(a[j].x-a[i].x);
        }
    }
    memset(f,MAXINT,sizeof(f));
    for (int i=1; i<=n; ++i) 
    {
        f[i][1]=s[1][i];
        for (int k=2; k<=m; ++k) 
            for (int j=k-1; j<i; ++j)
                    f[i][k]=min(f[j][k-1]+s[j+1][i],f[i][k]);
    }
    printf("%d\n",f[n][m]);
}
/* 4 2 1 1 2 2 3 6 0 7 */

回复

47 条回复,欢迎继续交流。

正在加载回复...