BZOJ1237: [SCOI2008]配对【贪心+DP】

dzy posted @ 2013年6月07日 16:08 in BZOJ with tags BZOJ 贪心 DP , 2021 阅读

排序、然后在上下3个中选、dp就好

然后我顺便学了写fread、真好、又快又实用又好写

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll inf=10000000000009LL;
#define abs(x) (((x)<0)?(-(x)):(x))
#define A(x,y) ((x==y)?inf:abs((x)-(y)))
ll n,a[100005],b[100005],f[100005];
char buf[2000000],*p=buf;
inline int getint(){
    ll r=0; while(*p<'0'||*p>'9')p++; while(*p>='0'&&*p<='9')r=r*10+*p++-48;return r;
}int main(){
    fread(p,1,2000000,stdin);
    n=getint(); for(ll i=1;i<=n;i++)a[i]=getint(),b[i]=getint();
    sort(a+1,a+n+1);    sort(b+1,b+n+1);
    f[1]=A(a[1],b[1]);  f[2]=min(f[1]+A(a[2],b[2]),A(a[1],b[2])+A(a[2],b[1]));
    for(ll i=3;i<=n;i++)f[i]=min(f[i-1]+A(a[i],b[i]),min(f[i-2]+A(a[i-1],b[i])+A(a[i],b[i-1]),min(f[i-3]+A(a[i],b[i-1])+A(a[i-1],b[i-2])+A(a[i-2],b[i]),f[i-3]+A(a[i],b[i-2])+A(a[i-1],b[i])+A(a[i-2],b[i-1]))));
    printf("%lld\n",f[n]==inf?-1LL:f[n]);    return 0;
}
Avatar_small
Emma 说:
2023年2月01日 20:30

This problem, BZOJ1237, can be solved using a combination of Greedy and Dynamic Programming algorithms. After sorting the top three and bottom three elements, the engagement rings Dynamic Programming approach is employed to find the optimal solution. Furthermore, while solving this problem, I also learned to write an efficient fread function that is both fast, practical, and easy to write.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter