14156: 【原4156】增强版田忌赛马

题目描述

author: LH 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4156

Description

自从赛马比赛，齐王被田忌打败之后。积蓄力量，驯养了N只马，并向田忌发出了挑战。田忌欣然接受，然而船新的规则是每场比赛，输的一方将要给赢的一方200两黄金，如果是平局的话，双方都不必拿出钱。现在每匹马的速度值是固定而且已知的，而齐王出马也不管田忌的出马顺序，他认为田忌是算不出来的。但是没想到是田忌认识了会写C++你，是选择向齐王低头，还是帮助田忌赢取更多的钱，都看你的表现了。但是助教都希望你做乱世的勇者，如果你没有拿到最多的钱，就剥夺你的分数。请问你应该如何帮助田忌安排自己的马去对抗齐王的马，才能赢取最多钱？

Input Format

第一行为一个正整数N，表示双方马的数量。第二行有N个整数表示田忌的马的速度。第三行的N个整数表示齐王的马的速度。

Output Format

仅有一行，为田忌赛马可能赢得的最多的钱，结果有可能为负。

Sample1 Input

3
92 83 71 
95 87 74

Sample1 Output

HINT:

好好审题，仔细骗分。

数据规模

对于30%的数据，1 \leq N \leq 5 保证接下来有20%的数据中不存在速度相同的马对于100%的数据，1 \leq N \lep 3000

WashSwang's solution

#include <iostream>
using namespace std;
int p[3001],q[3001],dp[3001][3001],m,n,ptr,ans,win,ping;
void qsort(int *s,int *t)
{
    if (s+1>=t) return;
    int i=0,j=int(t-s)-1,x=s[0];
    while (i<j)
    {
        while (i<j&&s[j]<=x) j--;
        if (i<j) s[i++]=s[j];
        while (i<j&&s[i]>=x) i++;
        if (i<j) s[j--]=s[i];
    }
    s[i]=x;
    qsort(s,s+i);
    qsort(s+i+1,t);
}
inline int cmp(int x,int y){
    if (x>y) return 1;
    if (x<y) return -1;
    return 0;
}
int main() {
    ios::sync_with_stdio(false);
    cin>>m;
    for (int i=0;i<m;++i) cin>>p[i];
    for (int i=0;i<m;++i) cin>>q[i];
    qsort(p,p+m);
    qsort(q,q+m);
    for (int i=1;i<=m;++i){
        for (int j=0;j<=i;++j)
        {
            dp[i][j]=-100000000;
            if (j>=1)
                dp[i][j]=max(dp[i-1][j-1]+cmp(p[j-1],q[i-1]),dp[i][j]);
            if (j<i)
                dp[i][j]=max(dp[i-1][j]+cmp(p[m-(i-j)],q[i-1]),dp[i][j]);
        }
    }
    ans=-100000000;
    for (int i=0;i<=m;++i)
        ans=max(dp[m][i],ans);
    cout<<ans*200;
    return 0;
}