自动搬运

查看原文

来自洛谷，原作者为

	北街的九命貓 **

搬运于2025-08-24 21:27:32，当前版本为作者最后更新于2018-04-04 20:30:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

#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]}这个方程把所有可能的贪心情况都表示出来了

希望可以帮助到你