题解 P1650 【田忌赛马】

OItby · 2019-02-12 10:54:07 · 题解

传送门(田忌赛马)

分析 : DP 或贪心

1.DP :

设f[i][j]表示齐王按从强到弱的顺序出马和田忌进行了i场比赛之后，从"头"取了j匹较强的马，从"尾"取了i-j匹较弱的马，所能获得的最大盈利。

则状态转移方程为:f[i][j] = max ( f[i-1][j] + g[n-(i-j)+1][i] , f[i-1][j-1] + g[j][i] ;

其中g[i][j]表示田忌的马和齐王的马分别按照由强到弱的顺序排序之后，田忌的第 i 匹马和齐王的第 j 匹马赛跑所能取得的盈利，胜为 200 ，负为 -200 ，平为 0。

图解：

动态规划方法一：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N=2001,INF=-2e+8;
int a[N],b[N],g[N][N],f[N][N];

bool Cmp(int n1,int n2) {return n1>n2;}

int main()
{
    int n,Ans,i,j; scanf("%d",&n);
    for (i=1;i<=n;++i) scanf("%d",&a[i]);
    for (i=1;i<=n;++i) scanf("%d",&b[i]);
    sort(a+1,a+n+1,Cmp),sort(b+1,b+n+1,Cmp);
    for (i=1;i<=n;++i)
        for (j=1;j<=n;++j)
        {
            if (a[i]>b[j]) g[i][j]=200;
            else if (a[i]==b[j]) g[i][j]=0;
                 else g[i][j]=-200;
            f[i][j]=INF;
        }
    for (i=1;i<=n;++i)
    {
        f[i][0]=f[i-1][0]+g[n-i+1][i];
        f[i][i]=f[i-1][i-1]+g[i][i];
        for (j=1;j<i;++j)
            f[i][j]=max(f[i-1][j]+g[n-i+j+1][i],f[i-1][j-1]+g[j][i]);
    }
    Ans=f[n][1];
    for (i=2;i<=n;++i) Ans=max(Ans,f[n][i]);
    printf("%d\n",Ans);
    return 0;
}

动态规划方法一的内存优化：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N=2001,INF=-2e+8;
int a[N],b[N],g[N][N],f[N];

bool Cmp(int n1,int n2) {return n1>n2;}

int main()
{
    int n,Ans,i,j; scanf("%d",&n);
    for (i=1;i<=n;++i) scanf("%d",&a[i]);
    for (i=1;i<=n;++i) scanf("%d",&b[i]);
    sort(a+1,a+n+1,Cmp),sort(b+1,b+n+1,Cmp);
    for (i=1;i<=n;++i)
        for (j=1;j<=n;++j)
        {
            if (a[i]>b[j]) g[i][j]=200;
            else if (a[i]==b[j]) g[i][j]=0;
                 else g[i][j]=-200;
        }
    for (i=1;i<=n;++i) f[i]=INF;
    for (i=1;i<=n;++i)
    {
        f[i]=f[i-1]+g[i][i];
        for (j=i-1;j>0;--j)
            f[j]=max(f[j]+g[n-i+j+1][i],f[j-1]+g[j][i]);
        f[0]=f[0]+g[n-i+1][i];
    }
    Ans=f[1];
    for (i=2;i<=n;++i) Ans=max(Ans,f[i]);
    printf("%d\n",Ans);
    return 0;
}

动态规划方法二：

解释见POJ 2287 【Tian Ji -- The Horse Racing】

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N=2001;
int a[N],b[N],dp[N][N];

bool Cmp(int x,int y) {return x>y;}

int main()
{
    int n,i,j; scanf("%d",&n);
    for (i=1;i<=n;++i) scanf("%d",&a[i]);
    for (i=1;i<=n;++i) scanf("%d",&b[i]);
    sort(a+1,a+n+1,Cmp),sort(b+1,b+n+1,Cmp);
    for (i=1;i<=n;++i)
        for (j=1;j<=n;++j)
            if (a[i]>b[j]) dp[i][j]=max(dp[i-1][j-1]+200,max(dp[i-1][j]-200,dp[i][j-1]-200));
            else if (a[i]==b[j]) dp[i][j]=max(dp[i-1][j-1],max(dp[i-1][j]-200,dp[i][j-1]-200));
                 else dp[i][j]=max(dp[i-1][j]-200,dp[i][j-1]-200);
    printf("%d\n",dp[n][n]);
    return 0;
}

2.\text{贪心} (推荐) : 分以下三种情况考虑：

如果田忌目前的最快马快于齐王目前的最快马，则两者比
如果田忌的最快马慢于齐王的最快马，则用田忌的最慢马与齐王的最快马比(减少损失)
如果田忌的最快马和齐王的最快马相等，分以下两种情况：
1. 若田忌的最慢马快与齐王的最慢马，两者比（能赢就赢呗）
2. 其他，用田忌的最慢马与齐王的最快马比（贡献最大）

贪心代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N=2001;
int a[N],b[N];

void Scanf(int &x)
{
    x=0;
    char s=getchar();
    while(s<'0'||s>'9') s=getchar();
    while(s>='0'&&s<='9') x=x*10+s-'0',s=getchar();
}

int main()
{
    int Ans,n,la,lb,ra,rb,i;
    Scanf(n);
    for (i=1;i<=n;++i) Scanf(a[i]);
    for (i=1;i<=n;++i) Scanf(b[i]);
    sort(a+1,a+n+1),sort(b+1,b+n+1);
    Ans=0,la=lb=1,ra=rb=n;
    for (i=1;i<=n;++i)
    {
        if (a[ra]>b[rb]) Ans+=200,--ra,--rb;
        else if (a[ra]<b[rb]) Ans-=200,++la,--rb;
             else if (a[la]>b[lb]) Ans+=200,++la,++lb;
                  else
                  {
                    if (a[la]<b[rb]) Ans-=200;
                    ++la,--rb;
                  }
    }
    printf("%d\n",Ans);
    return 0;
}

题解 P1650 【田忌赛马】

分析 : DP 或 贪心