POJ 1426 Find the Multiple(二维DP)

题目描述

总结

1. 编程之美讲了剪枝解法, 这里给出动规解法

2. dp[i][j]%n = j. dp[i][j] 是 mod n 余 j 的最小值

代码

/*
 * source.cpp
 *
 *  Created on: Apr 6, 2014
 *      Author: sangs
 */

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <memory.h>
using namespace std;

typedef unsigned long long LL;

LL dp[200][500];
LL cal(int n) {
	LL lastModed = 1;
	LL expr10 = 1;
	memset(dp, 0, sizeof(dp));

	dp[0][1] = 1;
	for(int i = 1; ; i ++) {
		for(int j = 1; j < n; j ++) {
			dp[i][j] = dp[i-1][j];
		}

		LL thisModed = (lastModed*(10%n))%n;
		lastModed = thisModed;
		expr10 *= 10;

		if(dp[i-1][thisModed] == 0) {
			dp[i][thisModed] = expr10;
		}
		//cout << dp[i][thisModed] << endl;

		for(int j = 1; j < n; j ++) {
			if(dp[i-1][j] == 0) {
				continue;
			}

			LL candy = (j + thisModed)%n;
			if(dp[i][candy] == 0) {
				dp[i][candy] = expr10 + dp[i-1][j];
			}
		}

		if(dp[i][0] != 0) {
			return dp[i][0];
		}
	}
	return 1;
}

int main() {
	freopen("input.txt", "r", stdin);
	int n;
	while(scanf("%d", &n) != EOF && n != 0) {
		LL res = cal(n);
		printf("%lld
", res);
	}
	return 0;
}