洛谷P2507 [SCOI2008]配对 题解(dp+贪心)
2024-08-28 22:14:32
洛谷P2507 [SCOI2008]配对 题解(dp+贪心)
标签:题解
阅读体验:https://zybuluo.com/Junlier/note/1299251
链接题目地址:洛谷P2507 [SCOI2008]配对
感觉是道很好的推断题
贪心
想到贪心的结论就很容易,没想到就很难做出来了
结论:对\(A,B\)数组分别排序之后,在\(A\)中选第\(i\)个数,与之配对的数一定在\(B[i-1]\)~\(B[i+1]\)内
其实证明是很好证的,在与你是否往这方面想了。。。
因为题目有一个很好的性质:\(A,B\)数列中数字各不相同
所以如果没有配对不相等的限制的话,我们肯定是排序直接减得答案是吧
那么有限制之后,就有机会让\(A[i]\)和\(B[i-1]\)或\(B[i+1]\)配对了吧,跳远了显然是不会更优的
动态规划
那么就可以直接\(dp\)了:\(dp[i]\)表示到第\(i\)号全部配对的最小答案
因为一个数可能与三个数配对,那么我们可以大力讨论\(dp\)了
对于限制,我们手写一个\(ABS\),如果差为0,返回\(Inf\)就\(ok\)
dp[i]=MIN(dp[i],dp[i-1]+ABS(A[i]-B[i]));
dp[i]=MIN(dp[i],dp[i-2]+ABS(A[i]-B[i-1])+ABS(A[i-1]-B[i]));
dp[i]=MIN(dp[i],dp[i-3]+ABS(A[i]-B[i-1])+ABS(A[i-1]-B[i-2])+ABS(A[i-2]-B[i]));
dp[i]=MIN(dp[i],dp[i-3]+ABS(A[i]-B[i-2])+ABS(A[i-1]-B[i-1])+ABS(A[i-2]-B[i]));
dp[i]=MIN(dp[i],dp[i-3]+ABS(A[i]-B[i-2])+ABS(A[i-1]-B[i])+ABS(A[i-2]-B[i-1]));
从上到下依次是:自己看一下吧。。。(草稿纸上玩结论,自己\(yy\),我懒得写了)
那么全部代码
不合法情况就是\(n==1\)并且\(A[1]==B[1]\)时
因为\(A,B\)数列中数字各不相同,所以\(n>1\)时一定可以另外配得到对
#include<bits/stdc++.h>
#define il inline
#define rg register
#define ldb double
#define lst long long
#define rgt register int
#define N 100050
using namespace std;
const lst Inf=1e15;
il int MAX(rgt x,rgt y){return x>y?x:y;}
il lst MIN(rg lst x,rg lst y){return x<y?x:y;}
il int read()
{
int s=0,m=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}
while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
int n;
lst A[N],B[N];lst dp[N];
il lst ABS(rg lst x){return x?(x>0?x:-x):(Inf);}
int main()
{
n=read();
for(rgt i=1;i<=n;++i)A[i]=read(),B[i]=read(),dp[i]=Inf;
if(n==1&&A[1]==B[1]){puts("-1");return 0;}
sort(&A[1],&A[n+1]),sort(&B[1],&B[n+1]);
dp[1]=ABS(A[1]-B[1]);
dp[2]=MIN(dp[1]+ABS(A[2]-B[2]),ABS(A[1]-B[2])+ABS(A[2]-B[1]));
for(rgt i=3;i<=n;++i)
{
dp[i]=MIN(dp[i],dp[i-1]+ABS(A[i]-B[i]));
dp[i]=MIN(dp[i],dp[i-2]+ABS(A[i]-B[i-1])+ABS(A[i-1]-B[i]));
dp[i]=MIN(dp[i],dp[i-3]+ABS(A[i]-B[i-1])+ABS(A[i-1]-B[i-2])+ABS(A[i-2]-B[i]));
dp[i]=MIN(dp[i],dp[i-3]+ABS(A[i]-B[i-2])+ABS(A[i-1]-B[i-1])+ABS(A[i-2]-B[i]));
dp[i]=MIN(dp[i],dp[i-3]+ABS(A[i]-B[i-2])+ABS(A[i-1]-B[i])+ABS(A[i-2]-B[i-1]));
}return printf("%lld\n",dp[n]),0;
}
最新文章
- 【前端】从输入URL到页面加载完成的过程中都发生了什么事情
- Skippr – 轻量、快速的 jQuery 幻灯片插件
- the comment lines of the blast tabular format
- 修改linux文件权限命令:chmod
- HDU 4292 Food 最大流
- PL/SQL显示行号和高亮当前行
- asp.net 使用my97 datepicker实现前后两个日期的范围界定
- javascript 的Date 格式化, 模仿shell中date命令的格式
- C/C++ char数组存储字符串内存地址
- jdbc hibernate myBatis比较
- redis绑定ip以及启动和查看启动状态
- 学号 20175212 《Java程序设计》第4周学习总结
- 前端使用 Nginx 反向代理彻底解决跨域问题
- 【AGC002E】Candy Piles 博弈论
- [HDFS Manual] CH6 HDFS Federation
- unix下ksh获取昨天的日期
- Oracle单机Rman笔记[1]---环境准备
- ftp命令详解补充
- Spring Http Invoker使用简介
- [UE4]创建KillInfoPanel