首页 > ACM题库 > HDU-杭电 > HDU 4398-Template Library Management-动态规划-[解题报告]HOJ
2015
05-24

HDU 4398-Template Library Management-动态规划-[解题报告]HOJ

Template Library Management

问题描述 :

As an experienced ACMer, you must have known the importance of "code template library". With the help of pre-printed code library, you can implement the complicated algorithms correctly and efficiently. However, the size of the library is strictly limited during the contest. For example, you can only take at most 25 pages of printed codes in World Finals. So you must choose carefully which code template should be included.
Now your team is participating a programming contest whose rules are slightly different from ICPC. This contest consists of N problems, and you must solved them in order: Before you solve the (i+1)th problem, you must solve the ith problem at first. And solving the ith problem requires a specified code template Ti.
You are allowed to hold M code templates only. At the beginning of the contest, your are holding templates numbered 1, 2, …, M. During the contest, if the problem you are trying to solve requires code template Ti, and Ti is happened at your hand (i.e, one of the M code templates you are holding is Ti), you can solve it immediately. On the other hand, if you are not holding Ti, you must call your friends who are outside the arena for help (yes, it is permitted, not cheating). They can give you the code template you need. Because you are only allowed to hold M code templates, after solving current problem, you must choose to drop the code you get from your friends just now, or to keep it and drop one of the M templates at your hand previously.
Given the problem sequence in the contest and the limitation M, you want finish all the problems with minimum number of calling your friends.

输入:

The first line of each test case contains two numbers N (1 <= N <= 100000) and M (1 <= M <= 100000). The second line contains N numbers T1, T2, …, TN (1 <= Ti <= 109), indicating the code templates required by each problem.

输出:

The first line of each test case contains two numbers N (1 <= N <= 100000) and M (1 <= M <= 100000). The second line contains N numbers T1, T2, …, TN (1 <= Ti <= 109), indicating the code templates required by each problem.

样例输入:

4 3
1 2 3 4
11 3
4 1 2 1 5 3 4 4 1 2 3

样例输出:

1
4

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=4389

题目大意:

求给定区间内,各位数字之和能被该数整除的数的个数。

解题思路:

数位dp。

注意用记忆化搜索做的时候,要保证记忆的状态能够重用并且不冲突,重要的是唯一确定性。

dp[i][j][k][l]表示后面还有i位,前面所有位数和为j,前面各位组成的数对l求模的余数为k,满足题目要求的数的种数。

本题的关键是,加一维mod数,使求余的数固定,以缩小存储的范围,同时满足唯一确定性,即可重用。

代码:

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF (1<<30)
#define PI acos(-1.0)
using namespace std;

int dp[10][82][82][82];
int pos[15];

int dfs(int cur,int lastf,int lastx,int mod,int flag)
{
   if(!cur)
   {
      if(lastx==0&&lastf==mod)
         return 1;
      return 0;
   }

   if(!flag&&dp[cur][lastf][lastx][mod]!=-1)
      return dp[cur][lastf][lastx][mod];

   int Max=flag?pos[cur]:9;
   int ans=0;

   for(int i=0;i<=Max;i++)
   {
      ans+=dfs(cur-1,lastf+i,(lastx*10+i)%mod,mod,flag&&i==Max);
   }
   if(!flag)
      dp[cur][lastf][lastx][mod]=ans;

   return ans;
}

int Cal(int n)
{
   int tt=0;

   while(n)
   {
      ++tt;
      pos[tt]=n%10;
      n/=10;
   }

   int temp=0;
   for(int i=1;i<=81;i++)
      temp+=dfs(tt,0,0,i,1);  //把各位数之和为i的满足题意数的个数全部找出来,简化的关键
   return temp;
}

int main()
{
   int t,a,b;

   scanf("%d",&t);
   memset(dp,-1,sizeof(dp));
   for(int ca=1;ca<=t;ca++)
   {
      scanf("%d%d",&a,&b);
      printf("Case %d: %d\n",ca,Cal(b)-Cal(a-1));
   }

   return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/cc_again/article/details/8872355