题解 P1021 【邮票面值设计】

MD_17L · 2019-07-12 18:02:56 · 题解

回溯搜索,DP

1. 首先分析得出邮票面值中,肯定有1分
2. 用a数组记录邮票面值,在DP中用b数组记录每种邮票面值所用的次数,x数组用于记录所更新的最优解
3. 初值a[1]=1;
4. 回溯

• 在js()函数中得到a数组中i-1种邮票面值连续的邮资最大值res
• 判断是否能更新
• 枚举从a[i-1]+1到res的邮票面值

  void find(int i)
  {
    int k,z;
    z=js(i-1);  
    if (i>n)
    {
        if (z-1>ans) 
        {
            ans=z-1;
            for (int j=1; j<=n; j++) x[j]=a[j];
        }
        return; 
    }
    for (k=z; k>=a[i-1]+1; k--)
    {
        a[i]=k;
        find(i+1);  
    }
  }

5. DP

• b数组初始化,赋上最大值
• a数组中第i种邮票面值的邮资数为1
• 从res=0开始枚举
• b[res]=min(b[res-a[i]]+1,b[res])
• 当b[res]超过最多能粘贴的邮票数时,退出循环

  int js(int t)
  {
    int i,res;
    for (i=1; i<=1000; i++) b[i]=1000000000;
    for (i=1; i<=t; i++) b[a[i]]=1;
    res=0;
    do
    {
        res++;
        for (i=1; i<=t; i++)
            if (res>a[i] && b[res-a[i]]+1<b[res])
                b[res]=b[res-a[i]]+1;
    }while (b[res]<=m);
    return res;
  }

最后,附上代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
int m,n,ans,a[1005],b[1005],x[1005];

 int js(int t)
{
    int i,res;
    for (i=1; i<=1000; i++) b[i]=1000000000;
    for (i=1; i<=t; i++) b[a[i]]=1;
    res=0;
    do
    {
        res++;
        for (i=1; i<=t; i++)
            if (res>a[i] && b[res-a[i]]+1<b[res])
                b[res]=b[res-a[i]]+1;
    }while (b[res]<=m);
    return res;
}

 void find(int i)
{
    int k,z;
    z=js(i-1);  
    if (i>n)
    {
        if (z-1>ans) 
        {
            ans=z-1;
            for (int j=1; j<=n; j++) x[j]=a[j];
        }
        return; 
    }
    for (k=z; k>=a[i-1]+1; k--)
    {
        a[i]=k;
        find(i+1);  
    }
}

 int main()
{
    scanf("%d%d",&m,&n);
    a[1]=1;
    find(2);    
    for (int i=1; i<=n; i++) printf("%d ",x[i]); printf("\n");
    printf("MAX=%d\n",ans);
    return 0;
}