AOJ 2607: Invest Master

久しぶりにPKUクオリティのオンラインジャッジ環境。(問題と呼べる条件を満たせない典型例)

1日ごとに全部売るのが最善であることが結構わかりにくい。

データが修正されたと書いてあるのに未だにデータに不備がある。AOJは機能もついているし何も損しないんだから最初から全部データ公開すべきだと思う。
結局データ作成者のコードを予測するだけの問題だった(ループの内外を逆にしたりtoの更新位置を変えたりすると明らかに不備っぽいケースで落ちる)。解法は結構よいだけにかなりもったいない。

#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[210000];
int d[11][11];
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<b;i++)for(int j=0;j<a;j++)scanf("%d",&d[i][j]);
	
	int now=c;
	for(int i=0;i<b-1;i++){
		for(int j=0;j<210000;j++)dp[j]=-99999999;
		dp[0]=0;
		int to=now;
	
		for(int k=0;k<a;k++){
			for(int j=0;j<=now;j++){
				dp[j+d[i][k]]=max(dp[j+d[i][k]],dp[j]+d[i+1][k]);
			}
		}
		for(int j=0;j<=now;j++)to=max(to,dp[j]+now-j);
		now=to;
	}
	printf("%d\n",now);
}