PKU 1973 「Software Company」

PKU解いてみた。
なぜこの問題をチョイスしたかというと、PKU Wiki*に載ってたから。
英語でも平気で読めるようになりたいものです。

「２分探索かな〜」とか「DPかな〜」とか思ってたら、
結局「２分探索＆DP」という結論に至った。

#include<cstdio>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 0; i <= n; i++)
using namespace std;

int main(){
	int t, n, m, x[100], y[100], dp[101][101], l, r, c, ny;
	
	scanf("%d",&t);
	
	rep(ti,t){
		scanf("%d%d",&n,&m);
		
		rep(i,n) scanf("%d%d",&x[i],&y[i]);
		
		l = 0; r = 1 << 29;
		while (l < r) {
			c = (l+r)/2;
			rrep(i,n) rrep(j,m) dp[i][j] = -1;
			dp[0][0] = 0;
			
			rep(i,n) rrep(j,m){
				if (c < x[i] * j) break;
				ny = (c - x[i] * j) / y[i];
				for (int k = j; k <= m; k++){
					if(dp[i][k-j] >= 0) dp[i+1][k] = max(dp[i+1][k],dp[i][k-j] + ny);
				}
			}
			
			if (dp[n][m] >= m) r = c; else l = c+1;
		}
		
		printf("%d\n",l);
	}
}

時間短縮をするには、

r = 1 << 29;

の 29 を 7 にしたりすれば（実験してみたところ、この辺が限界。）いいかも。