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 阅读(278)
评论(1) 编辑 收藏 引用 所属分类:
动态规划