oToToT的code收藏區

題目連結: http://tioj.infor.org/problems/1883 本題看起來很0/1背包吧，不過它跟普通的0/1背包不同的點在於它的物品是無限個的，因此這類問題又被稱作完全背包問題，那完全背包問題該如何做呢，不難發現原本0/1背包問題在滾動的時候要從後面滾是為了維護它不會重複取，不過我們現在不就是要讓它能重複取嗎?，所以其實就把0/1背包原本從後面倒過來做的，改成從前面做就好了 #include <bits/stdc++.h> using namespace std; struct skill{ int cost, damage; }; skill mySkills[1000 + 5]; int dmg[10000 + 5]; int main(){ int t; scanf("%d",&t); while(t--){ int w,b,n,m; scanf("%d%d%d",&w,&b,&n); for(int i=0;i<=w;i++){ dmg[i]=0; } for(int i=0;i<n;i++){ scanf("%d%d",&mySkills[i].cost,&mySkills[i].damage); } scanf("%d",&m); for(int i=0;i<n;i++){ mySkills[i].cost+=m; } for(int i=0;i<n;i++){ for(int j=mySkills[i].cost;j<w;j++){ dmg...

題目連結: http://tioj.infor.org/problems/1508 類背包問題，開一條長度為該序列總和的array，然後每次加入一個數都$O(sum)$跑過去比對新的數加進去後可以產生甚麼數，複雜度$O(n \Sigma n)$ #include <cstdio> #include <bitset> using std::bitset; inline long ABS(long a){ return a<0?-a:a; } int main() { int m,n; scanf("%d%d",&m,&n); while(m--){ int arr[100 + 10]; long sum=0; for(int i=0;i<n;i++){ scanf("%d",&arr[i]); sum+=arr[i]; } bitset<100000 + 10> b; b[0]=1; for(int i=0;i<n;i++){ bitset<100000 + 10>temp; for(int j=0;j<=sum;j++){ if(b[j]){ temp[j+arr[i]]=1; temp[ABS(j-arr[i])]=1; } } b=temp; } puts(b[0]?"Yes":"No"); } }