社区讨论
有大佬看一看这样为什么能过吗
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 条回复,欢迎继续交流。
正在加载回复...