「JoyOI1048」田忌赛马

2013年11月23日8,4292

题目描述

中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要赛马了，他们各派出N匹马，每场比赛，输的一方将要给赢的一方200两黄金，如果是平局的话，双方都不必拿出钱。现在每匹马的速度值是固定而且已知的，而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢取最多的钱？

输入

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

输出

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

样例输入

3 92 83 71 95 87 74

样例输出

200

9018题库的田忌赛马，如果田忌输了，输出0，且似乎n<=3000。JoyOI随意

本题原来是用贪心的思路，用田忌速度从小到大的每一匹马去战胜或打平齐王的最强的马

像这样

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int qw[10001]={0},tj[10001]={0};
    int n;
    cin>>n;
    long long ans=-n*200;
    for(int i=1;i<=n;i++)
       cin>>tj[i];
    for(int i=1;i<=n;i++)
       cin>>qw[i];
    sort(tj,tj+n+1);
    sort(qw,qw+n+1);
    for(int i=1;i<=n;i++)
    {
            for(int j=n;j>=1;j--)
            {
                    if(tj[i]>qw[j]){qw[j]=999999;ans+=400;break;}
                    else if(tj[i]==qw[j]){qw[j]=999999;ans+=200;break;}
                    }
            }
    cout<<max(0,ans);
    system("pause");
    return 0;
}

#include<iostream>

#include<algorithm>

using namespace std;

int main()

{

int qw[10001]={0},tj[10001]={0};

int n;

cin>>n;

long long ans=-n*200;

for(int i=1;i<=n;i++)

cin>>tj[i];

for(int i=1;i<=n;i++)

cin>>qw[i];

sort(tj,tj+n+1);

sort(qw,qw+n+1);

for(int i=1;i<=n;i++)

{

for(int j=n;j>=1;j--)

{

if(tj[i]>qw[j]){qw[j]=999999;ans+=400;break;}

else if(tj[i]==qw[j]){qw[j]=999999;ans+=200;break;}

}

cout<<max(0,ans);

system("pause");

return 0;

}

是有反例的，因为看不符合历史上赛马的典故，用这种方法下等马变成和下等马赛平了，显然不妥。

但是用最弱的马故意输最强的马当然也是不可取的。

网上有种贪心做法是这样

#include <iostream> 
#include <cstdio>
#include <algorithm> 
using namespace std; 
const int Max=10000; 
int tian[Max],king[Max];
int i,j,n; 
bool cmp(int a,int b) {return a>b;}
int main()
{ 
cin>>n;
for(i=1;i<=n;i++) {cin>>tian[i];}
for(i=1;i<=n;i++) {cin>>king[i];}
sort(tian+1,tian+1+n,cmp); 
sort(king+1,king+1+n,cmp);
int ans=0;
int ii,jj; 
for(i=1,j=1,ii=n,jj=n;i<=ii;)
    {
      if(tian[i]>king[j]){ans+=200;i++,j++;} 
      else if(tian[i]<king[j]){ans-=200;j++,ii--;}
      else
      {
        if(tian[ii]>king[jj])
        {
         ans+=200;
         ii--;jj--;
        } 
        else
        {
         if(tian[ii]<king[j]) 
         ans-=200;
         ii--,j++;
        }
      }
     } 
cout<<ans;
return 0;
}

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

const int Max=10000;

int tian[Max],king[Max];

int i,j,n;

bool cmp(int a,int b) {return a>b;}

int main()

{

cin>>n;

for(i=1;i<=n;i++) {cin>>tian[i];}

for(i=1;i<=n;i++) {cin>>king[i];}

sort(tian+1,tian+1+n,cmp);

sort(king+1,king+1+n,cmp);

int ans=0;

int ii,jj;

for(i=1,j=1,ii=n,jj=n;i<=ii;)

{

if(tian[i]>king[j]){ans+=200;i++,j++;}

else if(tian[i]<king[j]){ans-=200;j++,ii--;}

else

{

if(tian[ii]>king[jj])

{

ans+=200;

ii--;jj--;

}

else

{

if(tian[ii]<king[j])

ans-=200;

ii--,j++;

}

cout<<ans;

return 0;

}

1、开始也是先排序，可以使用sort快排；

2、然后将田忌最大的马与国王进行比较；

3、如果田忌最大的马大于国王，那么就胜场++；

4、如果田忌最大的马小于国王，那么就一定会输，所以用田忌最小的马输给国王最大的马；

5、如果田忌最大的马等于国王，那么就比较最小的马；

5。1、如果田忌最小的马大于国王，那么胜场++；

5。2、如果田忌最小的马小于国王，那么就输给国王；

5。3、如果田忌最小的马等于国王，就用田忌最小的马对国王最大的马，如果国王最大的马大，那么财产要减200；

还有动规的

1.思路
不妨用贪心思想来分析一下问题。因为田忌掌握有比赛的“主动权”，他总是根据齐王所出的马来分配自己的马，所以这里不妨认为齐王的出马顺序是按马的速度从高到低出的。由这样的假设，我们归纳出如下贪心策略：
如果田忌剩下的马中最强的马都赢不了齐王剩下的最强的马，那么应该用最差的一匹马去输给齐王最强的马。
如果田忌剩下的马中最强的马可以赢齐王剩下的最强的马，那就用这匹马去赢齐王剩下的最强的马。
如果田忌剩下的马中最强的马和齐王剩下的最强的马打平的话，可以选择打平或者用最差的马输掉比赛。
2.反例
光是打平的话，如果齐王马的速度分别是1 2 3，田忌马的速度也是1 2 3，每次选择打平的话，田忌一分钱也得不到，而如果选择先用速度为1的马输给速度为3的马的话，可以赢得200两黄金。
光是输掉的话，如果齐王马的速度分别是1 3，田忌马的速度分别是2 3，田忌一胜一负，仍然一分钱也拿不到。而如果先用速度为3的马去打平的话，可以赢得200两黄金。

3.解决方案
通过上述的三种贪心策略，我们可以发现，如果齐王的马是按速度排序之后，从高到低被派出的话，田忌一定是将他马按速度排序之后，从两头取马去和齐王的马比赛。有了这个信息之后，动态规划的模型也就出来了！

4.DP方程
设f[i,j]表示齐王按从强到弱的顺序出马和田忌进行了i场比赛之后，从“头”取了j匹较强的马，从“尾”取了i-j匹较弱的马，所能够得到的最大盈利。
状态转移方程如下：
F[I,j]=max{f[i-1,j]+c[n-(i-j)+1,i],f[i-1,j-1]+c[j,i]}
其中g[i,j]表示田忌的马和齐王的马分别按照由强到弱的顺序排序之后，田忌的第i匹马和齐王的第j匹马赛跑所能取得的盈利，胜为1，输为－1，平为0。
结果用最大的乘以200即可。

5.解释

为什么F[I,j]=max{f[i-1,j]+c[n-(i-j)+1,i],f[i-1,j-1]+c[j,i]}可以呢？

因为你无论怎么样都是从前或者从后面取马，而F[I,j]=max{f[i-1,j]+c[n-(i-j)+1,i],f[i-1,j-1]+c[j,i]}这个方程把所有可能的贪心情况都表示出来了。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int f[3001][3001],a[3001],b[3001],c[3001][3001];
int n,ans=0;
bool gz(int a,int b) {return a>b;}
int main()
{
    cin>>n;
    for(int i=0;i<=n;i++)
       for(int j=0;j<=n;j++)
          f[i][j]=-999999;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    sort(a+1,a+n+1,gz);
    sort(b+1,b+n+1,gz);
    for(int i=1;i<=n;i++)
       for(int j=1;j<=n;j++)
          if(a[i]>b[j])c[i][j]=1;
          else if(a[i]==b[j])c[i][j]=0;
          else c[i][j]=-1;
    f[0][0]=0;
    for(int i=1;i<=n;i++)
       for(int j=0;j<=i;j++)
          if(j>=1)f[i][j]=max(f[i-1][j]+c[n-(i-j)+1][i],f[i-1][j-1]+c[j][i]);
          else f[i][j]=f[i-1][j]+c[n-(i-j)+1][i];
    for(int i=0;i<=n;i++)
        ans=max(f[n][i],ans);
    cout<<ans*200;
    return 0;
}