生活随笔
收集整理的這篇文章主要介紹了
P1537 弹珠 背包可行性dp
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
傳送門
文章目錄
題意：
思路：
瘋狂水文章。
這個(gè)很明顯是個(gè)背包，我們開一個(gè)布爾數(shù)組，之后枚舉每組的個(gè)數(shù)，讓后枚舉1?61-61?6，再枚舉容量kkk，注意順序不能錯(cuò)了，讓后或一下就好啦。
還可以用bitsetbitsetbitset做，可能是因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">bitsetbitsetbitset每次移動(dòng)的NNN是固定的，而枚舉的sumsumsum是根據(jù)每次都不一樣的，所以bitsetbitsetbitset慢很多。。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#include<bitset>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=200010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int a
[10];
bool f
[N
];int main()
{
int id
=0;while(cin
>>a
[1]>>a
[2]>>a
[3]>>a
[4]>>a
[5]>>a
[6]&&(a
[1]+a
[2]+a
[3]+a
[4]+a
[5]+a
[6])) {printf("Collection #%d:\n",++id
);int sum
=0; memset(f
,false,sizeof(f
));for(int i
=1;i
<=6;i
++) sum
+=a
[i
]*i
;if(sum
%2==1) {puts("Can't be divided.");puts("");continue;}f
[0]=1;for(int i
=1;i
<=6;i
++) {for(int j
=1;j
<=a
[i
];j
++)for(int k
=sum
;k
>=0;k
--)f
[k
+i
]|=f
[k
];}if(f
[sum
/2]) puts("Can be divided.");else puts("Can't be divided.");puts("");}return 0;
}
#pragma GCC optimize(2)
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#include<bitset>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=200010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int a
[N
];
bitset
<N
>f
;int main()
{
int id
=0;while(cin
>>a
[1]>>a
[2]>>a
[3]>>a
[4]>>a
[5]>>a
[6]&&(a
[1]+a
[2]+a
[3]+a
[4]+a
[5]+a
[6])) {printf("Collection #%d:\n",++id
);int sum
=0; f
.reset();for(int i
=1;i
<=6;i
++) sum
+=a
[i
]*i
;if(sum
%2==1) {puts("Can't be divided.");puts("");continue;}f
[0]=1;for(int i
=1;i
<=6;i
++) {for(int j
=1;j
<=a
[i
];j
++)f
|=f
<<i
;}if(f
[sum
/2]) puts("Can be divided.");else puts("Can't be divided.");puts("");}return 0;
}
創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)
總結(jié)
以上是生活随笔為你收集整理的P1537 弹珠 背包可行性dp的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
