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年區域賽，西安賽區的B題，佳哥出的，犀利的DP。
一開始看此題，認為是數學方法加構造答案，推了一會就放棄了，之后看了同場那道網絡流的題，不過鑒于我對于那道網絡流思路相當惡心，就返回繼續思考這道題。
之后，發現這道題可以套用我昨天那道DP的轉移方程。
dp[i][j] = max{dp[i][j], dp[i + a[k]][(j * 10 + k) % m]}，其中，i表示用了i個木棍，j表示i個木棍構成的數mod m后是j，dp[i][j]表示構成這個最大數的長度。（因為是求mod，可以想到取mod后的狀態，這樣可以有效的減少狀態數目。）
說一下佳哥題解，也是讓我WA了無數次的坑。
關于那個dp[i][j]的轉移，我們可以看出每次轉移的時候，添加數字k是添加在了末尾一位，但我一開是dp是添加在了首位，佳哥說添加首位是錯誤的，但沒有給出證明，我找到了反例：11 6，應該是774，但我一開是得的是747，不過為什么錯，我無法證明了.....
在獲得上述轉移狀態后，我們可以用d數組記錄相應狀態下，最優解的最后一位，這樣我們輸出答案就可以從第一位遞歸尋找了。
至于無解的情況，只要n>=6都會有解，因為0是六根火柴......
其他思路：dp[i][j]記錄最優答案，這樣會涉及到大數運算。
代碼：
#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 閱讀(308)
評論(1) 編輯 收藏 引用 所屬分類:
動態規劃