K15160 象棋比赛（chess） —— 2023瑶海初中T4

题目描述

小K是学校的国际象棋爱好协会管理员，协会需要组建一支队伍去才加某比赛，这次比赛共需要2*a名队员，且a名队员先手（执白先行），a名队员后手（执黑后行）。

协会里有n名选手，他们先手和后手各有一个棋力值（用1至100表示）。协会主席请小K帮忙，选择出最好的2*a名选手组队，使得其中a名队员先手能力值之和 和另外a名队员后手能力值之和最大。

注意：先手选手在比赛中总是执白先行，而后手选手在比赛中总是执黑后行，一名选手不能兼报两项。

输入格式

输入文件：chess.in

第一行为两个正整数n和a，表示选手总数和要选择的选手数（2*a）；接下来n行，每行两个正整数p和q，分别表示一名选手先手和后手的能力值。

输出格式

输出文件：chess.out 

输出能力值之和的最大值

输入输出样例

输入样例1：

31 15

87 84

66 78

86 94

93 87

72 100

78 63

60 91

77 64

77 91

87 73

69 62

80 68

81 83

74 63

86 68

53 80

59 73

68 70

57 94

93 62

74 80

70 72

88 85

75 99

71 66

77 64

81 92

74 57

71 63

82 97

76 56

输出样例1：

2506

说明

20%数据：n<=100 

50%数据：n<=300

100%数据：n<=1000，2*a<=50，1<=p,q<=100

又是一道输入样例极其庞大的题。这题属于背包问题，实际上要研究的只是循环到的棋手是不要（既不加入先手，也不加入后手）、进先手还是进后手，随后判断即可

代码：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int dp[1010][51][51],n,a,p[1010],q[1010];
int main()
{
    cin>>n>>a;
    for(int i=1;i<=n;i++) cin>>p[i]>>q[i];
    dp[1][1][0]=p[1];
    dp[1][0][1]=q[1];
    for(int i=1;i<=n;i++)
        for(int j=0;j<=a;j++){
            for(int k=0;k<=a;k++){
                //dp[i][j][k]=max(dp[i-1][j][k],max(,));
                int x=0,y=0,z=0;
                x=dp[i-1][j][k];
                if(i>=j&&i>=j+k&&j>=1) y=dp[i-1][j-1][k]+p[i];
                if(i>=k&&i>=k+j&&k>=1) z=dp[i-1][j][k-1]+q[i];
                dp[i][j][k]=max(x,max(y,z));
            }
        }
    cout<<dp[n][a][a];
    return 0;
}

原文地址：https://blog.csdn.net/2301_79502610/article/details/142885497

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！