本题首先看上去像是一个贪心问题,对于齐王的马从大到小进行排序,然后对于齐王的马来说如果田的马没有比齐王马好的,那么就使用田最弱的马和他去比。如果有比齐王好的马就 去赢。
但在这里面有反例的存在,如果平局的时候怎么办?是直接平局好还是输掉好?例如:1 2 3,1 2 3来说算平局就是0,那么就没有输掉的效果好。例如:田:2 3,齐:1 3。如果算输的话就是0。但如果算平的话就是200。所以在平局的时候策略并不是唯一的。
在这里我们观察,田从齐王最大的那匹马开始,田无非就是上第一匹或者上最后一匹马那么也就是说选第一或最后一个两个选后最大的那一个。
那么dp[i][j]表示i到j这个区间能够获得的最大分数。那么状态转移方程为:dp[i][j] = max(dp[i+1][j]+cost(i,k), dp[i][j-1]+cost(j,k));。
//dp[i][j] = max(dp[i+1][j]+cost(i,k), dp[i][j-1]+cost(j,k)); #include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 10001; int n; int dp[maxn][maxn]; int tian[maxn]; int qi[maxn]; int cost(int tian_pos, int qi_pos) { if (tian[tian_pos]>qi[qi_pos]) return 200; if (tian[tian_pos]<qi[qi_pos]) return -200; if (tian[tian_pos]==qi[qi_pos]) return 0; return 0; } signed main() { cin>>n; for (int i=1;i<=n;i++) { cin>>tian[i]; } for (int i=1;i<=n;i++) { cin>>qi[i]; } sort(qi+1, qi+1+n); sort(tian+1, tian+1+n); for (int len = 1;len<=n;len++) { for (int l=1;l+len-1<=n;l++) { int r = l+len-1; int k = len-1+1; dp[l][r] = max(dp[l+1][r]+cost(l, k), dp[l][r-1]+cost(r,k)); } } cout<<dp[1][n]; return 0; }