传送门

分析

这个题和传统的田忌赛马不一样的地方就是多了平局情况,所有我们不难想到要用dp。我们先将两人的马均降序排列,用dpij表示考虑前i匹马,田忌有几匹马是按从大到小的顺序从头取的(剩下的是从尾部取的)。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
#define sp cout<<"---------------------------------------------------"<<endl;
int dp[][],a[],b[];
inline bool cmp(int x,int y){
return x>y;
}
inline int c(int x,int y){
if(x>y)return ;
else if(x<y)return -;
return ;
}
int main(){
int n,i,j;
scanf("%d",&n);
while(n!=){
memset(dp,,sizeof(dp));
for(i=;i<=n;i++)scanf("%d",&a[i]);
for(i=;i<=n;i++)scanf("%d",&b[i]);
sort(a+,a+n+,cmp);
sort(b+,b+n+,cmp);
for(i=;i<=n;i++){
for(j=;j<i;j++)
dp[i][j]=max(dp[i-][j-]+c(a[j],b[i]),dp[i-][j]+c(a[n-(i-j-)],b[i]));
dp[i][]=dp[i-][]+c(a[n-i+],b[i]);
dp[i][i]=dp[i-][i-]+c(a[i],b[i]);
}
int ans=-;
for(i=;i<=n;i++)
ans=max(ans,dp[n][i]);
printf("%d\n",ans);
scanf("%d",&n);
}
return ;
}

最新文章

  1. Linux下uniq命令的详解
  2. SQL2008&quot;阻止保存要求重新创建表的更改&quot;问题的解决
  3. ubuntu常用命令记录集
  4. Linux phpwind论坛的安装
  5. ExceptionExtensions
  6. PAT乙级 1010. 一元多项式求导 (25)
  7. android中的数据库操作
  8. 10635 - Prince and Princess
  9. selenium python 环境搭建
  10. SQL Server数据库连接类SQLHelper.cs
  11. 武汉科技大学ACM :1001: 华科版C语言程序设计教程(第二版)课后习题3.12
  12. Android常用控件之ExpandableList的使用
  13. 远程读取URL 建议用curl代替file_get_contents
  14. 计算机网络相关:应用层协议(二):HTTP
  15. Flask依赖和启动流程回顾
  16. 《温故而知新》JAVA基础六
  17. ArrayAdapter使用方法
  18. JS弹出对话框函数alert(),confirm(),prompt()
  19. Document对象中的一些重要的属性和方法(笔记)
  20. KnockoutJs学习笔记(二)

热门文章

  1. New Concept English three (50)
  2. Spring框架实现——远程方法调用RMI代码演示
  3. java-03方法课堂练习
  4. AfxExtractSubString 函数的相关问题
  5. k近邻算法C++二维情况下的实现
  6. WPF基本概念入门
  7. Admin.Admin/Login --- 后台项目中的管理员及登录模块
  8. HDU2841(容斥原理)
  9. 几种排序方式的java实现(02:希尔排序,归并排序,堆排序)
  10. Make 命令