Meaning: give the volume of $n $items and the maximum knapsack capacity of $m $, find out the number of schemes of $w\in [1,m] $knapsack after removing one item of $i $.
There are n items with volume of W1, W2,... WN. Due to her negligence, the ith item was lost. "How many ways can i use the remaining N – 1 items to fill a backpack with a volume of X?" This is a classic question. She wrote down the answer as Count(i, x), and wanted to get all the Count(i, x) tables with 1 < = i < = n, 1 < = x < = M.
Input: Line 1: two integers N (1 ≤ N ≤ 2 × 10 ^ 3) and M (1 ≤ M ≤ 2 × 10 ^ 3), quantity and maximum volume of goods.
Line 2: N integers W1, W2,... , WN, the volume of the article.
Output: a matrix of N × M, the last digit of Count(i, x).
Thinking: backpack, divide and rule.
Number of submissions: 1 (just mentioned in class)
Explanation:
Define $solve(s,l,r) $to represent the $s $layer, where the interval is $[l,r] $.
Recursion process: copy the previous level state to the current level, first add $[md+1,r] $items to the backpack, then $solve(s+1,l,md) $items, then clear the current level state, reset to the previous level state, then add $[l,md] $items to the backpack, then $solve(s+1,md+1,r) $, the boundary is $l==r $, at this time, only $l $items are not added to the backpack, so the output is good.
Code:
#include<cstdio> #include<iostream> #include<cstring> #include<cstring> #define R register int using namespace std; //You're weak. What's your right to rest #define ull unsigned long long #define ll long long #define pause (for(R i=1;i<=10000000000;++i)) #define In freopen("NOIPAK++.in","r",stdin) #define Out freopen("out.out","w",stdout) namespace Fread { static char B[1<<15],*S=B,*D=B; #ifndef JACK #define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++) #endif inline int g() { R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix; if(ch==EOF) return EOF; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix; } inline bool isempty(const char& ch) { return (ch<=36||ch>=127); } inline void gs(char* s) { register char ch; while(isempty(ch=getchar())); do *s++=ch; while(!isempty(ch=getchar())); } } using Fread::g; using Fread::gs; namespace Luitaryi { const int N=2010; int n,m; int f[15][N],w[N]; inline void solve(int s,int l,int r) { if(l==r) { for(R i=1;i<=m;++i) printf("%d",f[s-1][i]); putchar('\n'); return ; } R md=l+r>>1; memcpy(f[s],f[s-1],sizeof(f[s-1])); for(R i=md+1;i<=r;++i) for(R j=m;j>=w[i];--j) f[s][j]+=f[s][j-w[i]],f[s][j]%=10; solve(s+1,l,md); memcpy(f[s],f[s-1],sizeof(f[s-1])); for(R i=l;i<=md;++i) for(R j=m;j>=w[i];--j) f[s][j]+=f[s][j-w[i]],f[s][j]%=10; solve(s+1,md+1,r); } inline void main() { n=g(),m=g(); for(R i=1;i<=n;++i) w[i]=g(); f[0][0]=1; solve(1,1,n); } } signed main() { Luitaryi::main(); return 0; }
2019.07.14