Bigger is Better
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 559 Accepted Submission(s): 155
Problem Description
Bob has n matches. He wants to compose numbers using the following scheme (that is, digit 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 needs 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 matches):
Write a program to make a non-negative integer which is a multiple of m. The integer should be as big as possible.
Input
The input consists of several test cases. Each case is described by two positive integers n (n ≤ 100) and m (m ≤ 3000), as described above. The last test case is followed by a single zero, which should not be processed.
Output
For each test case, print the case number and the biggest number that can be made. If there is no solution, output -1.Note that Bob don't have to use all his matches.
Sample Input
Sample Output
Source
Recommend
lcy
06年區(qū)域賽，西安賽區(qū)的B題，佳哥出的，犀利的DP。
一開(kāi)始看此題，認(rèn)為是數(shù)學(xué)方法加構(gòu)造答案，推了一會(huì)就放棄了，之后看了同場(chǎng)那道網(wǎng)絡(luò)流的題，不過(guò)鑒于我對(duì)于那道網(wǎng)絡(luò)流思路相當(dāng)惡心，就返回繼續(xù)思考這道題。
之后，發(fā)現(xiàn)這道題可以套用我昨天那道DP的轉(zhuǎn)移方程。
dp[i][j] = max{dp[i][j], dp[i + a[k]][(j * 10 + k) % m]}，其中，i表示用了i個(gè)木棍，j表示i個(gè)木棍構(gòu)成的數(shù)mod m后是j，dp[i][j]表示構(gòu)成這個(gè)最大數(shù)的長(zhǎng)度。（因?yàn)槭乔髆od，可以想到取mod后的狀態(tài)，這樣可以有效的減少狀態(tài)數(shù)目。）
說(shuō)一下佳哥題解，也是讓我WA了無(wú)數(shù)次的坑。
關(guān)于那個(gè)dp[i][j]的轉(zhuǎn)移，我們可以看出每次轉(zhuǎn)移的時(shí)候，添加數(shù)字k是添加在了末尾一位，但我一開(kāi)是dp是添加在了首位，佳哥說(shuō)添加首位是錯(cuò)誤的，但沒(méi)有給出證明，我找到了反例：11 6，應(yīng)該是774，但我一開(kāi)是得的是747，不過(guò)為什么錯(cuò)，我無(wú)法證明了.....
在獲得上述轉(zhuǎn)移狀態(tài)后，我們可以用d數(shù)組記錄相應(yīng)狀態(tài)下，最優(yōu)解的最后一位，這樣我們輸出答案就可以從第一位遞歸尋找了。
至于無(wú)解的情況，只要n>=6都會(huì)有解，因?yàn)?是六根火柴......
其他思路：dp[i][j]記錄最優(yōu)答案，這樣會(huì)涉及到大數(shù)運(yùn)算。
代碼：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 101;
const int maxm = 3001;
const int used[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
typedef long long LL;
LL f[maxn][maxm], g[maxn][maxm];
LL n, m, i, j, k, u, v, Len, task;
LL max(LL i, LL j)
{
if (i > j) return i;
return j;
}
void printf(LL x, LL y)
{
LL u, v;
while (g[x][y] != 10)
{
u = x + used[g[x][y]];
v = (y * 10 + g[x][y]) % m;
cout << g[x][y];
x = u;
y = v;
}
cout << endl;
}
int main()
{
task = 0;
while (cin >> n && n)
{
cin >> m;
printf("Case %d: ", ++task);
memset(f, -1, sizeof(f));
Len = 0;
f[0][0] = 0;
for (i = 0; i <= n; ++i)
{
for (j = 0; j <= m - 1; ++j)
{
if (f[i][j] >= 0)
{
for (k = 0; k <= 9; ++k)
{
if (i + used[k] <= n)
{
if (i == 0 && k == 0) continue;
u = i + used[k];
v = (j * 10 + k) % m;
f[u][v] = max(f[u][v], f[i][j] + 1);
if (v == 0) Len = max(Len, f[u][v]);
}
}
}
}
}
memset(g, -1, sizeof(g));
for (i = n; i >= 0; --i)
{
for (j = 0; j <= m - 1; ++j)
{
if (f[i][j] >= 0)
{
if (f[i][j] == Len && j == 0)
{
g[i][j] = 10;
continue;
}
for (k = 9; k >= 0; --k)
{
if (i + used[k] <= n)
{
u = i + used[k];
v = (j * 10 + k) % m;
if (f[u][v] == f[i][j] + 1 && g[u][v] >= 0)
{
g[i][j] = k;
break;
}
}
}
}
}
}
if (g[0][0] > 0 && g[0][0] != 10) printf(0, 0);
else
if (n >= 6) cout << 0 << endl;
else
cout << -1 << endl;
}
return 0;
}
posted on 2011-10-15 22:14
LLawliet 閱讀(305)
評(píng)論(1) 編輯 收藏 引用 所屬分類(lèi):
動(dòng)態(tài)規(guī)劃