P1048 （C++代码）

解题思路:





注意事项:





参考代码:

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int read()
{    
int q=0;char ch=' ';    
while(ch<'0'||ch>'9')
ch=getchar();    
while(ch>='0'&&ch<='9')
q=q*10+ch-'0',ch=getchar();    
return q;
}
int n,ans;
int f[2005][2005],a[2005],b[2005];//a:田忌，b:齐王
int jg(int bb,int aa){//比较函数
    if(bb>aa)return -200;    
    if(aa>bb)return 200;    
    return 0;
}
    bool cmp(int x,int y)
    {
    return x>y;
    }
    int main()
    {    
    int i,j;
    n=read();    
    for(i=1;i<=n;i++)a[i]=read();    
    for(i=1;i<=n;i++)b[i]=read();
    sort(a+1,a+1+n,cmp);
    sort(b+1,b+1+n,cmp);    
    for(i=1;i<=n;i++)        
    for(j=1;j<=n;j++)f[i][j]=-999999999;    
    for(i=1;i<=n;i++)
    {
        f[i][i]=f[i-1][i-1]+jg(b[i],a[i]);//特别处理的两种情况：只出好马和只出驽马
        f[i][0]=f[i-1][0]+jg(b[i],a[n-i+1]);        for(j=1;j<i;j++)
        f[i][j]=max(f[i-1][j-1]+jg(b[i],a[j]),f[i-1][j]+jg(b[i],a[n-i+j+1]));//方程见上
    }    for(i=1;i<=n;i++)ans=max(ans,f[n][i]);    
         printf("%d",ans);    
         return 0;
}