最初だいぶ遠回りしちゃった。
https://www.hackerrank.com/contests/kodamanwithothers/challenges/1of5-weight
問題
重さ1/1,1/2,1/3,1/4,1/5の重りがa,b,c,d,e個ある。
これらの一部を使い、重さの合計をp/qにしたい。
各重さの選び方の組み合わせは何通りか。
解法
p/qをまず分母60に通分してしまおう。
あとは単なる個数制限付きナップサック問題になる。
int C[5],p,q; ll dp[6][6100000]; ll S[6100000]; void solve() { int i,j,k,l,r,x,y; string s; FOR(i,5) cin>>C[i]; cin>>p>>q; if(60%q) return _P("0\n"); p*=60/q; dp[0][0]=1; FOR(i,5) { x=60/(i+1); for(j=0;j<=6000000;j++) { S[j]=dp[i][j]; if(j>=x) S[j]+=S[j-x]; y=j-x*C[i]; if(y-x<0) dp[i+1][j]=S[j]; else dp[i+1][j]=S[j]-S[y-x]; } } cout<<dp[5][p]<<endl; }
まとめ
最初色々場合分けで解こうとしてしまった。