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

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




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(){
    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;
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