出来るだけ寝ていたい

1日最低12時間睡眠、寝たら負け

個数制限付き部分和問題

蟻本の初級編にあるDPの練習用問題。

漸化式は同じ立て方なので、

dp[i+1][j]=i番目まででjを作る際に余る最大のi番目の個数

とする。
DPテーブルを自分で書いてもらうと分かるように、ループの方向がj→j+a[i]の方向しか向いていないので配列の再利用が可能。
よってdp[j]という1次元配列でDPが可能である。

ひとまずやっている事は蟻本と変わらない。
しかし、自分はdp漸化式をソースコードとして書く際に右辺にiとjが来るように書いている(蟻本の場合は左辺)。

従って蟻本とは少し変わったプログラムを書いた。その時の記録である。

#include <bits/stdc++.h>
#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 sort(v,n) sort(v,v+n);
#define vsort(v) sort(v.begin(),v.end());
#define ll long long
#define pb(a) push_back(a)
#define fi first
#define se second
#define inf 999999999
using namespace std;
typedef pair<int,int> p;
typedef pair<ll,ll> lp;
bool is_uruu(int y) {
        return y % 4 == 0 && (y % 100 != 0 || y % 400 == 0);
}
const ll MOD=1e9+7;
const double PI=acos(-1.0);
//----------------------------------------------------------------------------------------------------------------------------------//

int n;
int a[100],m[100];
int k;
int dp[100001];
int main(){
        cin>>n;
        for(int i=0; i<n; i++) {
                cin>>a[i];
        }
        for(int i=0; i<n; i++) {
                cin>>m[i];
        }
        cin>>k;
        memset(dp,-1,sizeof(dp));
        dp[0]=0;
        for(int i=0; i<n; i++) {
                for(int j=0; j<=k; j++) {
                        if(dp[j]>=0) dp[j]=m[i];
                }
                for(int j=0; j<=k; j++) {
                        if(dp[j]>0 && j+a[i]<=k) {
                                dp[j+a[i]]=dp[j]-1;
                        }else if(dp[j]<0) {
                                dp[j]=-1;
                        }
                }
                for(int j=0; j<=k; j++) {
                        cout<<dp[j]<<" ";
                }
                cout<<endl;
        }
        if(dp[k]>-1) {
                cout<<"Yes"<<endl;
        }else{
                cout<<"No"<<endl;
        }
}

漸化式の書き方も色々あるそうなので、最終的にはどんな書き方でも書けるようにしたい。