关键词：
题目里给的范围是k<=4,但是官方数据并没有k==4的情况,导致一些奇奇怪怪的DP写法也能过。听说标程在k==4的时候有反例，掀桌….. 难怪COGS上k==4的数据答案是错的。
还是好好写个搜索吧:网上写法很多.我是每次沿着一条平行于坐标轴的直线将点集分割成两部分，并枚举k个矩形如何在两边分配。边界为k==1,扫一遍所有点找到最小的矩形。细节看代码吧.
但是这个搜索我也不能保证是对的,因为k==4有可能出现这种崎岖的最优方案:不存在一条平行于坐标轴且不和任何一个矩形相交的直线将4个矩形分成两部分.例如这样的最优方案：
贴个代码吧:递归的时候为了处理“将点集分成两部分”调了一堆memcpy….好在递归层数和点数都不多，不然常数炸天....
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=55; int x[maxn],y[maxn],seq[maxn]; inline int max(int a,int b){ return a>b?a:b; } inline int min(int a,int b){ return a<b?a:b; } bool cmp1(const int &a,const int &b){ return x[a]<x[b]; } bool cmp2(const int &a,const int &b){ return y[a]<y[b]; } struct node{ int x1,y1,x2,y2; node(){} node(int a,int b,int c,int d){ x1=a;y1=b;x2=c;y2=d; } }sol[10];int cnt=0; int work(int l,int r,int seq[]){ int minx=0x7f7f7f7f,miny=0x7f7f7f7f,maxx=0,maxy=0; for(int i=l;i<=r;++i){//printf("seq%d\n",seq[i]); minx=min(minx,x[seq[i]]);maxx=max(maxx,x[seq[i]]); miny=min(miny,y[seq[i]]);maxy=max(maxy,y[seq[i]]); } sol[++cnt]=node(minx,miny,maxx,maxy); return (maxx-minx)*(maxy-miny); } int s[1000][55];int tot=0; int dfs(int l,int r,int k,int seq[]){//printf("%d\n",k); if(k==1){ int tmp=work(l,r,seq); cnt--; return tmp; }else{ int ans=0x7f7f7f7f; sort(seq+l,seq+r+1,cmp1); for(int i=l;i<r;++i){ for(int j=1;j<k;++j){ ++tot; memcpy(s[tot],seq,sizeof(int)*55); ++tot; memcpy(s[tot],seq,sizeof(int)*55); if(x[seq[i]]!=x[seq[i+1]]){ int tmp=dfs(l,i,j,s[tot-1])+dfs(i+1,r,k-j,s[tot]); ans=min(ans,tmp); } --tot;--tot; //printf("---------------\n"); } }//printf("%d\n",ans); sort(seq+l,seq+r+1,cmp2); for(int i=l;i<r;++i){ for(int j=1;j<k;++j){ ++tot; memcpy(s[tot],seq,sizeof(int)*55); ++tot; memcpy(s[tot],seq,sizeof(int)*55); if(y[seq[i]]!=y[seq[i+1]]){ int tmp=dfs(l,i,j,s[tot-1])+dfs(i+1,r,k-j,s[tot]); ans=min(ans,tmp); } --tot;--tot; //printf("---------------\n"); } }//printf("%d\n",ans); return ans; } } int main(){ int n,k; scanf("%d%d",&n,&k); for(int i=1;i<=n;++i){ scanf("%d%d",x+i,y+i); } for(int i=1;i<=n;++i){ seq[i]=i; } printf("%d\n",dfs(1,n,k,seq)); return 0; }
cogs——t1175.[顾研noip]旅游电车
http://www.cogs.pro/cogs/problem/problem.php?pid=1175★★☆ 输入文件：buss.in 输出文件：buss.out 简单对比时间限制：1s 内存限制：256MB【问题描述】Henryy国正致力于首都的一个旅游电车建设工程。首都有... 查看详情
cogs466.[noip2009]细胞分裂
466.[NOIP2009]细胞分裂★★ 输入文件：cell.in 输出文件：cell.out 简单对比时间限制：1s 内存限制：128MB【问题描述】 Hanks博士是BT(Bio-Tech，生物技术)领域的知名专家。现在，他... 查看详情
cogs——t1265.[noip2012]同余方程
http://cogs.pro/cogs/problem/problem.php?pid=1265★☆ 输入文件：mod.in 输出文件：mod.out 简单对比时间限制：1s 内存限制：128MB【题目描述】求关于x的同余方程ax≡1(modb)的最小正整数解。【输入格式... 查看详情
cogs983.[noip2003]数字游戏
983.[NOIP2003]数字游戏★☆ 输入文件：numgame.in 输出文件：numgame.out 简单对比时间限制：1s 内存限制：128MB题目描述丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多... 查看详情
cogs1811.[noip2014]螺旋矩阵
★ 输入文件：matrixc.in 输出文件：matrixc.out 简单对比时间限制：1s 内存限制：256MB【题目描述】 MLE：#include<iostream>#include<cstdio>#include<algorithm>usingn 查看详情
ac日记——[noip2015]运输计划cogs2109
[NOIP2015]运输计划 思路： 树剖+二分； 代码：#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;#definemaxn300005#defineINF0x7fffffffintn,deep[m 查看详情
cogs2104.[noip2015]神奇的幻方
★ 输入文件：2015magic.in 输出文件：2015magic.out 简单对比时间限制：1s 内存限制：256MB1#include<iostream>2#include<cstdio>3inta[41][41];4intmain()5{6freopen("2015magic.i 查看详情
cogs2104.[noip2015]神奇的幻方
★ 输入文件：2015magic.in 输出文件：2015magic.out 简单对比时间限制：1s 内存限制：256MB 模拟一开始数组开小了。。屠龙宝刀点击就送#include<cstdio>intn,h[1600],l[1600],hf[45][45];intmain() 查看详情
cogs1264.[noip2012]开车旅行（70分暴力）
1264.[NOIP2012]开车旅行★★☆ 输入文件：drive.in 输出文件：drive.out 简单对比时间限制：2s 内存限制：128MB【题目描述】小A和小B决定利用假期外出旅行，他们将想去的城市从1到N编号，且编号... 查看详情
cogs106.[noip2003]加分二叉树(区间dp)
106.[NOIP2003]加分二叉树★☆ 输入文件：jfecs.in 输出文件：jfecs.out 简单对比时间限制：1s 内存限制：128MB【问题描述】设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,&... 查看详情
tyvj4239[noip2015提高组dayt3]斗地主
P2668斗地主题目描述牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的A到K加上大小王的共54张牌来进行的扑克牌游戏。在斗地主中，牌的大小关系根据牌的数码表示如下：3<4<5<6<7<... 查看详情
cogs74.[noip2006]明明的随机数(splay小练习。。)
☆ 输入文件：random.in 输出文件：random.out 简单对比时间限制：1s 内存限制：128MB【问题描述】 明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算... 查看详情
[noip2012]摆花
1270.[NOIP2012]摆花http://cogs.pro/cogs/problem/problem.php?pid=1270★ 输入文件：flower.in 输出文件：flower.out 简单对比时间限制：1s 内存限制：128MB【题目描述】小明的花店新开张，为了吸引顾客，他想在... 查看详情
[noip2014]子矩阵
1812.[NOIP2014]子矩阵http://www.cogs.pro/cogs/problem/problem.php?pid=1812★★★ 输入文件：submatrix.in 输出文件：submatrix.out 简单对比时间限制：1s 内存限制：256MB【题目描述】最暴力的算法是枚举选 查看详情
[noip2013]货车运输
1439.[NOIP2013]货车运输http://cogs.pro/cogs/problem/problem.php?pid=1439★★☆ 输入文件：truck.in 输出文件：truck.out 简单对比时间限制：1s 内存限制：128MB【题目描述】 【来源】CCF全国信息学奥林匹 查看详情
[noip2008]传球游戏
1011.[NOIP2008]传球游戏http://cogs.pro/cogs/problem/problem.php?pid=1011★ 输入文件：ballg.in 输出文件：ballg.out 简单对比时间限制：1s 内存限制：50MB【问题描述】上体育课的时候，小蛮的老师经常带着同... 查看详情
bzoj4318osu!&&tyvj1952easy
链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4318，http://www.tyvj.cn/p/1952其实这两个题题意差不多，游戏都一样（一样吗？计分方式都不一样），都是连续的数值价值会变为多次方，只不过一个是变成三次方，一个是变成二次方。对O... 查看详情
cogs2096.不平凡的许愿树
【题目描述】noip要到了，大家来到许愿树前。这个许愿树不仅仅是许愿树，还有未卜先知的功能。众OIer问许愿树：“不平凡的许愿树，CCF告诉我们noip中会有两道题目从Openjudge上选择，你能不能告诉我是哪两道题。”许愿树想了... 查看详情