算法入门-田忌赛马

田忌赛马

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;
}
全部评论

相关推荐

Lorn的意义:你这种岗位在中国现在要么牛马天天加班,要么关系户进去好吃好喝,8年时间,真的天翻地覆了,对于资本来说你就说一头体力更好的牛马,哎,退伍没有包分配你真的亏了。
点赞 评论 收藏
分享
05-14 20:34
门头沟学院 Java
窝补药贝八股:管他们,乱说,反正又不去,直接说680
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务