「JoyOI1617 / 2062」偷葡萄(grape)

描述 Description

fox来到了一排葡萄架下,葡萄架上有很多葡萄(n串),它想将一部分葡萄偷走.
每串葡萄都有一个价值,当然,由于有酸有甜,葡萄的价值可能为正,也可能为负.
当然,为了让农夫看不出来,fox规定,每k串葡萄中,它最多选b串,但是由于fox是比较贪心的,每连续k串葡萄中,它会最少选a串
例如n=5 k=3 a=1 b=2时,在第1–第3串葡萄中,fox只能选1或2串,在第2–第4串葡萄中,fox也只能选1或2串.
图1的选法是不合法的,因为2–4中选出了3串葡萄
图2的选法也是不合法的,因为1–3中选出了0串葡萄
而图3的选法是合法的.
现在,fox要选出一些葡萄,而农夫得到剩余的葡萄,由于fox有嫉妒心理,希望让fox得到的价值减去农夫得到的价值的差值最大

输入格式 InputFormat

第一行整数n,k,a,b
第二行n个整数表示每串葡萄的价值

输出格式 OutputFormat

仅一行,表示答案

样例输入 SampleInput [复制数据]

2 1 0 1
2 -2

1 2	2 1 0 1 2 -2

样例输出 SampleOutput [复制数据]

4

1

4

数据范围和注释 Hint

对于10%的数据         n<=10
对于另外30%的数据     a=0,b=k
对于100%数据       n<=10000,0<=a<=b<=k<=10

来源 Source

来源：fox_pro 开学欢乐赛

题解

状压dp，预处理出可行状态，然后转移

我的做法是从前往后转移，并且每次删掉状态第1位，分类讨论状态第K位

注意ans初始值要设为-inf

#include<iostream>
#include<cstdio>
#define inf 0x7fffffff
#define ll long long 
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 x*f;
}
int n,K,a,b,ed;
ll tot,ans=-inf;
int s[25],v[10005];
ll f[10005][1025];
bool jud[1025];
bool judge(int x)
{
	int cnt=0;
	for(int i=1;i<=K;i++)
	    if((s[i-1]|x)==x)cnt++;
	return (cnt>=a&&cnt<=b);
}
int main()
{
	n=read(),K=read(),a=read(),b=read();
    s[0]=1;
    for(int i=1;i<=15;i++)
        s[i]=(s[i-1]<<1);
	for(int i=1;i<=n;i++)
        v[i]=read(),tot+=v[i];
    ed=(1<<K)-1;
    for(int i=0;i<=ed;i++)
        jud[i]=judge(i);
    for(int i=0;i<=n;i++)
        for(int j=0;j<=ed;j++)
            f[i][j]=-inf;
    f[0][0]=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<=ed;j++)
            if(f[i][j]!=-inf)
            {
            	int to=(j>>1);
            	if(jud[to]||i+1<K)f[i+1][to]=max(f[i+1][to],f[i][j]);
            	to|=s[K-1];
            	if(jud[to]||i+1<K)f[i+1][to]=max(f[i+1][to],f[i][j]+v[i+1]);
            }
    for(int j=0;j<=ed;j++)ans=max(ans,f[n][j]);
    printf("%lld",2*ans-tot);
	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

43

44

45

46

47

48

49

50

51

52

#include<iostream>

#include<cstdio>

#define inf 0x7fffffff

#define ll long long

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 x*f;

}

int n,K,a,b,ed;

ll tot,ans=-inf;

int s[25],v[10005];

ll f[10005][1025];

bool jud[1025];

bool judge(int x)

{

int cnt=0;

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

if((s[i-1]|x)==x)cnt++;

return (cnt>=a&&cnt<=b);

}

int main()

{

n=read(),K=read(),a=read(),b=read();

s[0]=1;

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

s[i]=(s[i-1]<<1);

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

v[i]=read(),tot+=v[i];

ed=(1<<K)-1;

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

jud[i]=judge(i);

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

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

f[i][j]=-inf;

f[0][0]=0;

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

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

if(f[i][j]!=-inf)

{

int to=(j>>1);

if(jud[to]||i+1<K)f[i+1][to]=max(f[i+1][to],f[i][j]);

to|=s[K-1];

if(jud[to]||i+1<K)f[i+1][to]=max(f[i+1][to],f[i][j]+v[i+1]);

}

for(int j=0;j<=ed;j++)ans=max(ans,f[n][j]);

printf("%lld",2*ans-tot);

return 0;

}

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

描述 Description

输入格式 InputFormat

输出格式 OutputFormat

样例输入 SampleInput [复制数据]

样例输出 SampleOutput [复制数据]

数据范围和注释 Hint

来源 Source

分类目录

热门文章

Myfriends

近期评论