算法入门-田忌赛马

田忌赛马

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

相关推荐

07-03 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
风中翠竹:真的真的真的没有kpi。。。面试官是没有任何kpi的,捞是真的想试试看这个行不行,碰碰运气,或者是面试官比较闲现在,没事捞个人看看。kpi算HR那边,但是只有你入职了,kpi才作数,面试是没有的。
双非有机会进大厂吗
点赞 评论 收藏
分享
那一天的Java_J...:他本来公司就是做这个的,不就是正常的游戏客户端和服务器开发,软硬件联动,有啥恶心不恶心的,提前告诉你就是怕你接受不了,接受不了就没必要再往后走流程浪费时间,虽然这公司是一坨。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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