POJ-1742

• problem

1742 -- Coins

• code

#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <sstream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <complex>
#include <vector>
#include <cstdio>
#include <cmath>
#include <utility>
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define ll long long
#define pb(a) push_back(a)
#define fi first
#define se second
using namespace std;

template<class T>inline string toString(T x){
        ostringstream sout; sout<<x; return sout.str();
}
const ll MOD=1e9+7;
const int inf=(ll)1e9;
const double PI=acos(-1.0);

int dp[2][100001];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.precision(10);
    cout<<fixed;
    int n,m;
    while(cin>>n>>m){
    	if(n==0 && m==0)return 0;
    	int a[101],c[101];
    	for(int i=0;i<n;i++){
    		cin>>a[i];
    	}
    	for(int i=0;i<n;i++){
    		cin>>c[i];
    	}
    	for(int i=0;i<2;i++){
    		for(int j=0;j<100001;j++){
    			dp[i][j]=-1;
    		}
    	}
    	dp[0][0]=c[0];
    	for(int i=0;i<n;i++){
    		for(int j=0;j<=m;j++){
    			if(dp[i%2][j]>0 && j+a[i]<=m){
    				dp[i%2][j+a[i]]=max(dp[i%2][j]-1,dp[i%2][j+a[i]]);
    			}
    			if(dp[i%2][j]>=0){
    				dp[(i+1)%2][j]=c[i+1];
    			}else dp[(i+1)%2][j]=-1;
    		}
    	}
    	int ans=0;
    	//cerr<<"================"<<endl;
    	//for(int i=0;i<=n;i++){
    	//	for(int j=0;j<=m;j++){
    	//		cerr<<dp[i][j]<<" ";
    	//	}
    	//	cerr<<endl;
    	//}
    	for(int i=1;i<=m;i++){
    		if(dp[n%2][i]>=0)ans++;
    	}
    	cout<<ans<<endl;
    }
    return 0;
}

• 感想

最初は配列の再利用せずに提出してMLE。
だから、自力でやったことがない配列の再利用を恐る恐る自力でやってみた。
結局は漸化式がiとi+1のところでしかやり取りしてないから2個しか用意してなくても使いまわせるじゃん？みたいな？感じなのかな？
よく分かってないから、そんな感じの認識。
にしても、案外学習が遅い自分なりには自力でACできてまあ良かった。