题意

• 齐王和田忌各有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;
}