算法入门-田忌赛马
田忌赛马
https://ac.nowcoder.com/acm/problem/235246
题意
- 齐王和田忌各有n匹马，田忌赢得200，输得-200，平局不得钱，请你安排顺序，解出可获得的最大钱数
思路
-
先将齐王和田忌的马降序排序
-
贪心：对于齐王的第k匹马，田忌如果能赢就直接选当前第一匹马，如果不能赢就选择最后一匹马
-
对于平局的情况，选择第一匹和最后一匹都有可能导致错误决策
-
由于每一次都只有可能拿第一个和最后一个，所以剩下的一定是一个连续的区间，考虑动态规划
-
对于齐王的第k匹马
-
其中，k这个维度是没有意义的，从三维视角，固定k以后的每一层是不相交的，且总共会合成一个三角形，可以压缩到二维平面，k与l,r有关，限制方程为
,化简得
最终状态转移方程（01滚动）
AC代码
#include<bits/stdc++.h>
using namespace std;
int dp[2][202020];
int q[202020];
int t[202020];
int cost(int a,int b){
if(t[a]>q[b]) return 200;
else if(t[a]==q[b])return 0;
else return -200;
}
bool cmp(int a,int b){return a>b;}
int main(){
int n;
cin >> n ;
for(int i=1;i<=n;i++) cin >> t[i];
for(int i=1;i<=n;i++) cin >> q[i];
sort(t+1,t+1+n,cmp);
sort(q+1,q+1+n,cmp);
for(int i=1;i<=n;i++){
dp[i%2][i]=cost(i,n);
}
//r-l+1==n-k+1
for(int l=n-1;l>=1;l--){
for(int r=l+1;r<=n;r++){
dp[l%2][r]=max(dp[(l+1)%2][r]+cost(l,n-r+l),dp[l%2][r-1]+cost(r,n-r+l));
}
}
cout << dp[1][n] << endl ;
return 0;
}
