编译通过...

├ 测试数据 01：答案正确... 0ms

├ **测试数据 **02：答案正确... 0ms

├ **测试数据 **03：答案正确... 431ms

├ **测试数据 **04：答案正确... 338ms

├ **测试数据 **05：答案正确... 103ms

├ **测试数据 **06：答案正确... 72ms

├ **测试数据 **07：答案正确... 9ms

├ **测试数据 **08：答案正确... 9ms

├ **测试数据 **09：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：962ms

把f[i1][i2][i3][i4][i5]五维背包换成f[5000000]，做一个函数hash:

int hash(int a,int b,int c,int d,int e)

{

return a*(v[2]+1)*(v[3]+1)*(v[4]+1)*(v[5]+1)+b*(v[3]+1)*(v[4]+1)*(v[5]+1)+c*(v[4]+1)*(v[5]+1)+d*(v[5]+1)+e;

}

思想同hash。

全局可能的状态数极多，但单个测试点的状态数较少。

用秦九韶小小优化一下hash的代码：

hash := (((i5*(v[4]+1)+i4)*(v[3]+1)+i3)*(v[2]+1)+i2)*(v[1]+1)+i1;

楼下同志，发题解程序小心号封锁。现在不同原来了...

状态压缩.

下标取：i1+i2*(v1+1)+i3*(v1+1)*(v2+1)+i4*(v1+1)*(v2+1)*(v3+1)+i5*(v1+1)*(v2+1)*(v3+1)*(v4+1)

i1,i2,i3,i4,i5是5种药的量

v1,v2,v3,v4,v5是每种药物的上限

给每种不同的包的组合编一个唯一的号即可　数组稍微开大一点　因为考虑包的容积可以为０

背包

问一下，为什么按那样用二进制顺次连接起来的totv就不会超过5000000？这是很明显可以超过的，而且按照不同的顺序得到的totv会不一样。

不过二进制的思想是不错的，拍了一会过了。

standard里面的背包貌似是可重复的（难道我看错了？）

那个5000000是其实虚指……但是到考试中也可能是m很大但是n很小，这就是数据范围=。=

=。=

正因为小于5000000所以我才说是小于5000000，具体得估计比500000还要小……

二进制是为了编码实现要简便点，看着也很爽……

如果是可重复背包那我的程序就错了……

楼下的....那样子可以压成一个数，但是怎么压回来？

这怎么背包 数组要多大！！！

rqnoj的题

也是那次模拟赛我唯一ac的题....

背包问题

今天太晚了，第一又被抢走了明天来A

状态压缩,把500W的空间彻底利用起来

居然__*一次*__就过了

记录信息
评测状态 Accepted
题目 P1426 兴奋剂检查
递交时间 2013-10-18 22:12:30
代码语言 C++
评测机 上海红茶馆
消耗时间 1216 ms
消耗内存 39708 KiB
评测时间 2013-10-18 22:12:32

评测结果
编译成功

测试数据 #0: Accepted, time = 31 ms, mem = 39708 KiB, score = 11

测试数据 #1: Accepted, time = 78 ms, mem = 39708 KiB, score = 11

测试数据 #2: Accepted, time = 468 ms, mem = 39704 KiB, score = 11

测试数据 #3: Accepted, time = 359 ms, mem = 39708 KiB, score = 11

测试数据 #4: Accepted, time = 109 ms, mem = 39708 KiB, score = 11

测试数据 #5: Accepted, time = 109 ms, mem = 39708 KiB, score = 11

测试数据 #6: Accepted, time = 31 ms, mem = 39708 KiB, score = 11

测试数据 #7: Accepted, time = 31 ms, mem = 39704 KiB, score = 11

测试数据 #8: Accepted, time = 0 ms, mem = 39708 KiB, score = 12

Accepted, time = 1216 ms, mem = 39708 KiB, score = 100

代码
#include <iostream>
using namespace std;
int a1,a2,a3,a4,a5;
int j,k;
int ans,m,n;
int a[10000001];
int b[201][6];
int f[6];
int main()
{
cin>>n>>m;
for (int i=1;i<=m;i++)
{
cin>>f[i];
}
for (int i=1;i<=n;i++)
for (int j=0;j<=m;j++)
cin>>b[i][j];
for (int i=1;i<=n;i++)
for (a1=f[1];a1>=b[i][1];a1--)
for (a2=f[2];a2>=b[i][2];a2--)
for (a3=f[3];a3>=b[i][3];a3--)
for (a4=f[4];a4>=b[i][4];a4--)
for (a5=f[5];a5>=b[i][5];a5--)
{
j=(((a1*(f[2]+1)+a2)*(f[3]+1)+a3)*(f[4]+1)+a4)*(f[5]+1)+a5;
k=((((a1-b[i][1])*(f[2]+1)+(a2-b[i][2]))*(f[3]+1)+(a3-b[i][3]))*(f[4]+1)+(a4-b[i][4]))*(f[5]+1)+a5-b[i][5];
if (a[k]+b[i][0]>a[j])
{
a[j]=a[k]+b[i][0];
if (a[j]>ans) ans=a[j];
}
}
cout<<ans<<endl;
return 0;
}

编译通过... 

├ 测试数据 01：答案正确... (31ms, 39412KB) 

├ 测试数据 02：答案正确... (94ms, 39408KB) 

├ 测试数据 03：答案正确... (546ms, 39408KB) 

├ 测试数据 04：答案正确... (421ms, 39408KB) 

├ 测试数据 05：答案正确... (141ms, 39412KB) 

├ 测试数据 06：答案正确... (156ms, 39412KB) 

├ 测试数据 07：答案正确... (63ms, 39412KB) 

├ 测试数据 08：答案正确... (63ms, 39412KB) 

├ 测试数据 09：答案正确... (0ms, 39408KB) 

---|---|---|---|---|---|---|---|-

Accepted / 100 / 1518ms / 39412KB 

view sourceprint?

01

#include

02

using namespace std;

03

int a1,a2,a3,a4,a5;

04

int j,k;

05

int ans,m,n;

06

int a[10000001];

07

int b[201][6];

08

int f[6];

09

 

10

 

11

 

12

 

13

 

14

 

15

 

16

 

17

 

18

 

19

 

20

 

21

int main()

22

{

23

    cin>>n>>m;

24

    for (int i=1;i>f[i];

27

    }

28

    for (int i=1;ib[i][j];

31

    for (int i=1;i=b[i][1];a1--)

33

            for (a2=f[2];a2>=b[i][2];a2--)

34

                for (a3=f[3];a3>=b[i][3];a3--)

35

                    for (a4=f[4];a4>=b[i][4];a4--)

36

                        for (a5=f[5];a5>=b[i][5];a5--)

37

                        {

38

                            j=(((a1*(f[2]+1)+a2)*(f[3]+1)+a3)*(f[4]+1)+a4)*(f[5]+1)+a5;

39

                            k=((((a1-b[i][1])*(f[2]+1)+(a2-b[i][2]))*(f[3]+1)+(a3-b[i][3]))*(f[4]+1)+(a4-b[i][4]))*(f[5]+1)+a5-b[i][5];

40

                            if (a[k]+b[i][0]>a[j])

41

                            {

42

                                a[j]=a[k]+b[i][0];

43

                                if (a[j]>ans) ans=a[j];

44

                            }

45

                        }

46

    cout

晕菜

不会 怎么压的？

哪位牛指导一下~~~~~

QQ：392106999 谢谢！

一不小心..

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

就ac了.

哪个大牛能解释一下，为什么HASH压缩不会冲突。

PS：感谢PUPPY

编译通过...

├ 测试数据 01：答案正确... 56ms

├ 测试数据 02：答案正确... 150ms

├ 测试数据 03：运行超时...

├ 测试数据 04：运行超时...

├ 测试数据 05：答案正确... 666ms

├ 测试数据 06：答案正确... 712ms

├ 测试数据 07：答案正确... 400ms

├ 测试数据 08：答案正确... 447ms

├ 测试数据 09：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：78 有效耗时：2431ms

Flag 　　Accepted

题号 　　P1426

类型(?) 　　动态规划

通过 　　163人

提交 　　817次

通过率 　　20%

难度 　　2

???

什么都没改再来一次

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 556ms

├ 测试数据 04：答案正确... 400ms

├ 测试数据 05：答案正确... 88ms

├ 测试数据 06：答案正确... 103ms

├ 测试数据 07：答案正确... 25ms

├ 测试数据 08：答案正确... 41ms

├ 测试数据 09：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1213ms