博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
洛谷P1650 赛马
阅读量:5875 次
发布时间:2019-06-19

本文共 1465 字,大约阅读时间需要 4 分钟。

洛谷P1650 赛马

我们将马从大到小排序,对于齐王的马,有一种贪心原则

要么赢得最经济,要么输得最彻底
所以对于齐王的马,田忌有两种出战原则,要么出当前最强的马
要么出当前最弱的马
动态规划 f[i][j] 表示齐王的前i匹马出战
而田忌的最强的前 j 匹马出战

 

1 #include 
2 #define For(i,j,k) for(int i=j;i<=k;i++) 3 using namespace std ; 4 5 const int N = 2011,inf = 1e9 ; 6 int n,m ; 7 int a[N],b[N],f[N][N] ; 8 9 inline int read() 10 {11 int x = 0 , f = 1 ; 12 char ch = getchar() ; 13 while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 14 while(ch>='0'&&ch<='9') { x = x * 10+ch-48 ; ch = getchar() ; } 15 return x * f ; 16 }17 18 inline bool cmp(int a,int b) 19 {20 return a > b ; 21 }22 23 inline int check(int x,int y) 24 {25 if(a[x]>b[y]) return 200 ; 26 else if(a[x]==b[y]) return 0 ; 27 else return -200 ; 28 }29 30 int main() 31 {32 n = read() ; 33 For(i,1,n) a[i]=read() ; 34 For(i,1,n) b[i]=read() ; 35 sort(a+1,a+n+1,cmp) ; 36 sort(b+1,b+n+1,cmp) ; 37 For(i,0,n) 38 For(j,0,n) f[i][j] = -inf ; 39 f[0][0] = 0 ; 40 For(i,1,n) {41 f[i][i] = f[i-1][i-1]+check(i,i) ; 42 f[i][0] = f[i-1][0] +check(n-i+1,i) ; 43 For(j,1,i-1) {44 f[i][j]=max(f[i][j],f[i-1][j-1]+check(j,i)) ; 45 f[i][j]=max(f[i][j],f[i-1][j]+check(n-(i-j)+1,i)) ; 46 }47 }48 int ans = 0 ; 49 For(i,0,n) 50 ans = max(ans,f[n][i]) ; 51 printf("%d\n",ans) ; 52 return 0 ; 53 }

 

转载于:https://www.cnblogs.com/third2333/p/7614280.html

你可能感兴趣的文章
微信JSSDK上传图片
查看>>
java集合类深入分析之Queue篇(1)
查看>>
bond的7种模式原理
查看>>
C语言的简单函数定义与调用
查看>>
二维码
查看>>
7-24
查看>>
spring中的JdbcTemplate简单记录
查看>>
pygame连载
查看>>
寒冰linux视频教程笔记12 计划任务
查看>>
在C盘上安装安装Windows Server 2008
查看>>
Servlet3.1 edr 规范中文版下载
查看>>
Magento支付宝插件V6.1旗舰版发布,支持即时到账、担保交易,新增订单重新支付功能!...
查看>>
基于Annotation方式的SpringMVC4+Spring4+Hibernate4
查看>>
我的友情链接
查看>>
git add 项目文件 改动
查看>>
GAP
查看>>
C/C++中的引用和指针
查看>>
CISCO PIX515 在企业应用中的布署
查看>>
学习笔记-Exchange Web Service API-概述
查看>>
idea创建Web项目
查看>>