「JoyOI1608」小熊分糖

背景 Background

AndyBear 生日模拟赛第二题

描述 Description

晴朗的上午，小熊BIBO抱着一罐糖，出去找好朋友，两只小兔子。从小熊家出来，穿过小树林，在一个有向日葵的路口向右拐，这就是小兔子家了。小熊BIBO见到好朋友，开心的不得了，BIBO要做的第一件事，是分糖，因为大熊说过，好东西是不可以独享的。
糖罐里有N颗糖，小熊BIBO要挑出m颗来给两只小兔子，剩下的留着自己吃。对于这n颗糖中的每一颗，这两只小兔子都有各自的喜欢程度Ai和Bi。小熊BIBO想让挑出来这m颗糖的“Ai和”与“Bi和”的差尽量小，在满足“Ai和”与“Bi和”的差最小的情况下呢，要让“Ai和”与“Bi和”的和尽量大。小熊BIBO可不擅长算数，所以想请你告诉她，如果选m颗糖，“Ai和”与“Bi和”的最小差是多少，还有在满足这个最小差的情况下，最大和是多少。

输入格式 InputFormat

输入文件的第一行，有两个数字，n和m，代表小熊BIBO要从n颗糖中挑出m颗。
接下来有n行，每行两个数字Ai和Bi，代表第i颗糖的Ai值和Bi值。

输出格式 OutputFormat

输出应该包含两行数字。
第一行是这m颗糖的“Ai和”与“Bi和”的差的最小值。
第二行是在满足第一行答案的选糖所有方案中，“Ai和”与“Bi和”的最大值。

请注意，本题中提及的“差”，均是指两数相减的绝对值，即 |A-B|。

样例输入 SampleInput [复制数据]

1

2

3

4

5

4 2

1 2

2 3

4 1

6 2

样例输出 SampleOutput [复制数据]

2
10

解释：挑出的是第二颗和第三颗糖。

1

2

3

4

2

10

解释：挑出的是第二颗和第三颗糖。

数据范围和注释 Hint

对于10%的数据, 0<n<=5,
对于30%的数据，0<n<=50,
对于100%的数据, 0<n<=200, 0<m<=20, 0<=Ai,Bi<=20.
输入数据均为整数。

题解

f[i][j][k]表示前i个取j个然后a[i]和比b[i]和大（40-k）时a[i]与比b[i]和的和的最大值

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define inf 0x7fffffff
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return f*x;
}
int n,m,ans1=inf,ans2;
int a[205],b[205];
int f[205][25][85];
int main()
{
    n=read();m=read();
    for(int i=0;i<=n;i++)
        for(int j=0;j<=20;j++)
            for(int k=0;k<=80;k++)
                f[i][j][k]=-inf;
    f[0][0][40]=0;
    for(int i=1;i<=n;i++)
        a[i]=read(),b[i]=read();
    for(int i=1;i<=n;i++)
        for(int k=0;k<=20;k++)
            for(int j=0;j<=80;j++)
            {
                int t=a[i]-b[i];
                f[i][k][j]=f[i-1][k][j];
                if(j-t<=80&&j-t>=0&&k>0)
                   f[i][k][j]=max(f[i][k][j],f[i-1][k-1][j-t]+a[i]+b[i]);
            }
    for(int j=0;j<=80;j++)
        if(f[n][m][j]>=0)
            if(abs(j-40)<ans1)ans1=abs(j-40),ans2=f[n][m][j];
            else if(abs(j-40)==ans1)ans2=max(f[n][m][j],ans2);
    printf("%d\n%d",ans1,ans2);
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#define inf 0x7fffffff

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return f*x;

}

int n,m,ans1=inf,ans2;

int a[205],b[205];

int f[205][25][85];

int main()

{

n=read();m=read();

for(int i=0;i<=n;i++)

for(int j=0;j<=20;j++)

for(int k=0;k<=80;k++)

f[i][j][k]=-inf;

f[0][0][40]=0;

for(int i=1;i<=n;i++)

a[i]=read(),b[i]=read();

for(int i=1;i<=n;i++)

for(int k=0;k<=20;k++)

for(int j=0;j<=80;j++)

{

int t=a[i]-b[i];

f[i][k][j]=f[i-1][k][j];

if(j-t<=80&&j-t>=0&&k>0)

f[i][k][j]=max(f[i][k][j],f[i-1][k-1][j-t]+a[i]+b[i]);

}

for(int j=0;j<=80;j++)

if(f[n][m][j]>=0)

if(abs(j-40)<ans1)ans1=abs(j-40),ans2=f[n][m][j];

else if(abs(j-40)==ans1)ans2=max(f[n][m][j],ans2);

printf("%d\n%d",ans1,ans2);

return 0;

}

hzwer.com _ Home | http://hzwer.com

背景 Background

描述 Description

输入格式 InputFormat

输出格式 OutputFormat

样例输入 SampleInput [复制数据]

样例输出 SampleOutput [复制数据]

数据范围和注释 Hint

分类目录

热门文章

Myfriends

近期评论