AOJ 2607 Invest Master

#include<bits/stdc++.h>
#define fi first
#define se second
#define show(x) cerr<<#x<<"="<<x<<"\n"
typedef long long ll;
using namespace std;
//const ll MOD=(ll)1e9+7;
//const ll inf=(ll)1e14;
const int dy[]={1,0,-1};
const int dx[]={1,0,-1};
int n,m,h,w;
string s;
int a[11][11];
int dp[11][100001];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
  FILE *stream1;
  //FILE *stream2;
  stream1=freopen("in","r",stdin);
  //stream2=freopen("out","w",stdout);
  if(stream1==NULL)return 0;
  //if(stream2==NULL)return 0;
#endif
  cin>>w>>h>>n;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin>>a[i][j];
    }
  }
  for(int i=0;i<h;i++)for(int j=0;j<100001;j++)dp[i][j]=-1;
  dp[0][0]=n;
  for(int i=0;i<h-1;i++){
    for(int j=0;j<100001;j++){
      if(dp[i][j]==-1)continue;
      for(int k=0;k<w;k++){
        int cont=1;
        while(dp[i][j]-cont*a[i][k]>=0){
          dp[i][j+cont*a[i+1][k]]=max(dp[i][j]-cont*a[i][k],dp[i][j+cont*a[i+1][k]]);
          dp[i+1][0]=max(dp[i+1][0],dp[i][j]-cont*a[i][k]+cont*a[i+1][k]);
          cont++;
        }
      }
      dp[i+1][0]=max(dp[i][j]+j,dp[i+1][0]);
    }
  }
  cout<<dp[h-1][0]<<endl;
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}

dp[何日目か][その次の日得られる利益の合計]=今日中に使える残りの金額
みたいな漸化式でやったらたまたま出来ました。
嬉しい。