田忌赛马 - 洛谷
首先对大王的进行从高到低排序，也顺便对田忌进行排序。如果田忌头部马能够战胜本局大王马，那么就出队，否则选择最末尾的马，那么每局也就有两种情况，选择末尾马，选择头部马。dp[i][j]代表第i轮时，田忌前面出了j匹马。他可以本轮出第j匹马，也可以i-1轮出到j匹马，本轮出第min(n,n-(i-j)+1)的马。【因为为了凑够i匹，必须从最后选出剩余的】
第一轮时， dp[1][1] dp[1][0]（最后一匹马）分别处理
第二轮dp[2][1] 依靠dp[1][1]与dp[1][0]来转移 ,也就是说，两局头选一马，可以第一局选，第二局选。 dp[2][2]依靠dp[1][1]来转移dp[2][0]依靠dp[1][0]来转移，符合比赛规则与顺序。
同理，第三轮 dp[3][1]依靠dp[2][1],dp[2][0]转移，三局选一马，可以第三局选，可以第一局，第二局选，但都包含在dp[2][1]之内
里面其实蕴含了贪心的思想，也就是本局大王的马能怼掉就必须用当前最牛的马怼掉，否则用最差的马送掉。那万一我们能怼的时候放弃这一局呢，显然当前最牛的马会去抢夺次牛马的生意，做出的贡献仍然是一局。但剩余的马如果无法怼掉这一局的大王马，就不如先用最强的怼掉，那万一次强的也能怼掉本局大王马呢，那么最强与次强其实是等价的，他们都能怼掉剩余的马，用哪个都一样。
#include
# includeusing namespace std;
typedef long long int ll;
int dp[2010][2010];
int a[2010],b[2010];
int c[2010][2010];
bool cmp(int a,int b)
{
return a>b;
}
int main()
{int n;
cin>>n;
for(int i=1;
i<=n;
i++)
cin>>a[i];
for(int i=1;
i<=n;
i++)
cin>>b[i];
sort(a+1,a+1+n,cmp);
sort(b+1,b+1+n,cmp);
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]
【动态规划|P1650 田忌赛马[普及+提高】DP】
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 剑指offer进阶|剑指offer103（最少的硬币数目）
- 动态规划|dp+贪心+滚动数组优化——植物大战僵尸
- 蓝桥杯|蓝桥python——方格分割【2017 第四题】
- 算法|不会有人2022年还不懂栈吧（）
- 《力扣周赛题解》|【解题报告】力扣 第 277 场周赛
- 动态规划|AcWing 271. 杨老师的照相排列（简单DP）+ 十一届蓝桥杯B组试题E--矩阵
- 蓝桥杯练习题|分解质因数
- 动态规划|LeetCode 300.最长递归子序列
- 菜鸟刷题|蓝桥杯每日一题——最大字段和问题（动态规划）