Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
第一次1Adp问题。纪念个。附菜鸟2000+ms代码,求指教#include <iostream> #include <algorithm> using namespace std; int A[128]; int C[128]; bool dp[100001]; int main(int argc, char *argv[]) { int n,m; while(cin>>n>>m && n||m) { for(int i=1;i<=n;++i) cin>>A[i]; for(int i=1;i<=n;++i) cin>>C[i]; memset(dp,0,sizeof(bool)*(m+1)); dp[0]=true; for(int i=1;i<=n;++i) { if(C[i]*A[i]>=m) { for(int j=A[i];j<=m;++j) dp[j]|=dp[j-A[i]]; } else { int k=1; int M=C[i]; while(k<M) { for(int j=m;j>=k*A[i];--j) dp[j]|=dp[j-k*A[i]]; M-=k; k*=2; } for(int j=m;j>=M*A[i];--j) dp[j]|=dp[j-M*A[i]]; } } cout<<count(dp+1,dp+m+1,true)<<endl; } } Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator