AtCoder ABC #310 (freee プログラミングコンテスト2023) : Ex - Negative Cost

初手で発想が間違っていた。
https://atcoder.jp/contests/abc310/tasks/abc310_h

問題

N個の魔法があり、それぞれ魔力の増減量と敵へのダメージが与えられる。
初期状態で魔力は0であり、魔力を負にするような魔法を唱えることはできない。

敵に合計ダメージH以上を与えるのに必要な、最小魔法詠唱回数を求めよ。

解法

魔力増減量の絶対値の最大値をLとする。
まず、以下を求めよう。
f(i) := i回の魔法で、魔力が負になることなく敵に与えられるダメージの最大値
これは魔力の現在値を0～2Lの範囲だけ考えればよく、f(1)～f(2L)を求めるのにO(NL^2)で済む。

あらゆる魔法の使い方は、並べ替えるとf(1)～f(2L)相当の組み合わせで可能である。
そこで、f(1)～f(2L)を求められれば、f(4L^2)までもO(L^3)で求められる。

次に、Hダメージを与えるのに基本的には効率f(i)/iが最大となる組み合わせを連打すればよく、端数分だけ他の魔法を使えばよい。
そこで端数分と連打するiを総当たりし、最大値を求めよう。

int N;
ll H;
int C[303],D[303];
ll dp[608][608];
ll ma[606];
ll cand[606*606];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>H;
	FOR(i,N) {
		cin>>C[i]>>D[i];
		C[i]=-C[i];
	}
	
	FOR(x,606) FOR(y,603) dp[x][y]=ma[x]=-1LL<<61;
	dp[0][0]=0;
	FOR(x,601) {
		FOR(y,603) if(dp[x][y]>=0) {
			FOR(i,N) if(y+C[i]>=0&&y+C[i]<=600) chmax(dp[x+1][y+C[i]],dp[x][y]+D[i]);
			chmax(ma[x],dp[x][y]);
		}
	}
	ll ret=1LL<<61;
	FOR(x,601*301) {
		if(cand[x]>=H) {
			ret=min(ret,(ll)x);
		}
		else {
			for(y=1;y<=600;y++) if(ma[y]>=0) {
				chmax(cand[x+y],cand[x]+ma[y]);
				ret=min(ret,x+(H-cand[x]+ma[y]-1)/ma[y]*y);
			}
		}
		
	}
	cout<<ret<<endl;
}

まとめ

双対グラフから最大フローとかかなーと迷走してしまった。