现在的位置: 首页 > 综合 > 正文

HDOJ 2929 Bigger is Better

2017年11月23日 ⁄ 综合 ⁄ 共 2667字 ⁄ 字号 小 中 大 ⁄ 评论关闭
DP。。。。好难的DP。。。

Bigger is Better

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 749    Accepted Submission(s): 190


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):
HDOJ 2929 Bigger is Better - qhn999 - 码代码的猿猿

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
6 3
5 6
0
 


Sample Output
Case 1: 111
Case 2: -1
 


Source
 


Recommend
lcy
 

 

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int MaxN=120,MaxM=3200,MOD=100000000;
const int a[10]={6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
typedef int BIG[7];
BIG dp[MaxN][MaxM];

void BIG2B(BIG a,BIG b)
{
    for(int i=0;i<7;i++)
        a=b;
}

bool BIGless(BIG a,BIG b)
{
    for(int i=6;i>=0;i--)
    {
        if(a<b) return true;
        if(a>b) return false;
    }
    return false;
}

void BIGmultipe(BIG x,int k,BIG ret)
{
    for(int i=0;i<7;i++)
        ret=x;
    for(int i=0;i<7;i++)
    {
        ret=ret*10+k;
        k=ret/MOD;
        ret=ret%MOD;
    }
}

void GET_DP(int n,int m)
{
    memset(dp,0,sizeof(dp));
    for(int i=0;i<MaxN;i++) for(int j=0;j<MaxM;j++) dp[j][0]=-1;
    dp[0][0][0]=0;
    BIG ret,t;
    memset(ret,0,sizeof(ret)); ret[0]=-1;

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(dp[j][0]==-1) continue;
            for(int k=0;k<10;k++)
            {
                if(a[k]+i>n) continue;
                BIGmultipe(dp[j],k,t);
                if(BIGless(dp[i+a[k]][(j*10+k)%m],t))
                {
                    BIG2B(dp[i+a[k]][(j*10+k)%m],t);
                    if((j*10+k)%m==0)
                    {
                        if(BIGless(ret,t))
                            BIG2B(ret,t);
                    }
                }
            }
        }
    }

    if(ret[0]==-1)
    {
        puts("-1");
    }
    else
    {
        int i;
        for(i=6;i>=0;i--)
            if(ret) break;
        if(i==-1)
        {
            puts("0");
        }
        else
        {
            for(;i>=0;i--)
            {
                printf("%d",ret);
            }
            putchar(10);
        }
    }
}

int main()
{
    int n,m,cas=1;
    while(scanf("%d",&n)!=EOF&&n)
    {
        scanf("%d",&m);
        printf("Case %d: ",cas++);
        GET_DP(n,m);
    }
    return 0;
}

* This source code was highlighted by YcdoiT. ( style: Codeblocks )

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞