HeinzHuang

Eudaimonia

0%

SameDigits（Topcoder 7705）

Posted on Edited on In

题目描述：

令函数f(x)(x为正整数)，返回值为x的位数中的最长连续相同的数字长度，比如f(344488)=3,f(123)=1. 现在给你两个正整数n与k, 要求计算出有多少个位数不大于n的数x满足f(x)=k. 返回的答案向44444444取模

输入

两个正整数n,k. n,k≤1000

输出

输出答案

思路：

比较有趣的一道DP题，对于状态的定义比较困难，若能想到定义方式，那么状态转移比较简单了。

自己当初就是状态定义的太差导致想了很久。。

状态定义

定义DP[i][j][flag]为还需要填i个数，已填了的数中结尾有j个连续相同的数，是否已出现过k个连续相同的数了，有多少种填发。 由此可知，答案便是9×(dp[k-1][1][0]+..+dp[n-1][1][0] (其实就是填了第一个数有九种方案，剩下的数有 dp [i-1] [1] [0] 种方法)

状态转移

接下来就是状态转移了，其实状态知道了后转移就不难了，最初dp [0] [k] [0] ,dp [0] [1..k] [1] 的值都为1（整个数都填完了，只需考虑它符不符合条件），然后每次删掉最后一个数，枚举最后连续长度l，若是小于k的那么就从l+1和1中转移(1说明与前面的数不同，连续长度变回1),若刚好等于k，那么只能从1中转移，因为连续长度不能超过k，此时的flag注意要是1，因为已经达到一次k的长度了！

这样这题就做完了，看似十分简单，但要想到这样写个人认为是很困难的，要仔细揣摩揣摩。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
#include <iostream>
#include <sstream>
#include <ctime> 
using namespace std;
#define FOR(i,l,r) for(int i=(int)l;i<=(int)r;i++)
#define DOR(i,r,l) for(int i=(int)r;i>=(int)l;i--)
#define loop(i,n) for(int i=0;i<(int)n;i++)
#define mms(a,x) memset(a,x,sizeof a)
#define sf scanf
#define pf printf
#define N 1005
#define P 44444444
#define ll long long
int K;
ll dp[N][N][2];
class SameDigits {
public:
	int howMany(int n,int k){
		K=k;
		ll ans=0;
		mms(dp,-1);
		FOR(i,1,k-1){
			dp[0][i][1]=1;
			dp[0][i][0]=0;
		}
		dp[0][k][1]=dp[0][k][0]=1;
		FOR(i,1,n){//仍需要填几个数 
			FOR(j,1,k-1){//已填的数中的最后有多少个相同的数 
				dp[i][j][1]=(dp[i-1][j+1][1]+9*dp[i-1][1][1])%P;
				dp[i][j][0]=(dp[i-1][j+1][0]+9*dp[i-1][1][0])%P;
				//若没有达到k个，那么有两种情况：与最后一个相同(j变为j+1)，或者不同(j变为1)
			}
			dp[i][k][1]=dp[i][k][0]=9*dp[i-1][1][1]%P;
			//当达到k个时,下一个的j必须是1，flag变为1表示已经达到过k了！
		}
		FOR(i,k,n)ans=(ans+9*dp[i-1][1][0])%P;
		return (int)ans;
	}
};

另外，这题不用循环DP，用递归也可以，两份我都写了一遍这里也把代码上一 下，思路几乎一样，就是逆过来想，另外就是运行速度会慢些，因为要递归。。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
#include <iostream>
#include <sstream>
#include <ctime>
using namespace std;
#define FOR(i,l,r) for(int i=(int)l;i<=(int)r;i++)
#define DOR(i,r,l) for(int i=(int)r;i>=(int)l;i--)
#define loop(i,n) for(int i=0;i<(int)n;i++)
#define mms(a,x) memset(a,x,sizeof a)
#define sf scanf
#define pf printf
#define N 1005
#define P 44444444
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int,int>pii;
typedef vector<pii> vpii;
const int inf=0x20202020;
const ll mod=1000000007;
const db eps=1e-9;
const db pi=3.1415926535897932384626;
ll powmod(ll a,ll b){ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int K;
ll dp[N][N][2];
ll f(int n,int lst,bool flag){
	if(dp[n][lst][flag]!=-1)return dp[n][lst][flag];
	if(!n){
		if(flag||lst==K)return dp[n][lst][flag]=1;
		else return dp[n][lst][flag]=0;
	}
	if(lst==K)return dp[n][lst][flag]=9*f(n-1,1,1)%P;
	return dp[n][lst][flag]=(f(n-1,lst+1,flag)+9*f(n-1,1,flag))%P;
}
int howMany(int n,int k){
	K=k;
	ll ans=0;
	mms(dp,-1);
	FOR(i,k,n)ans=(ans+9*f(i-1,1,0))%P;
	return (int)ans;
}
class SameDigits {
public:
	int howMany(int n, int k) {
		K=k;
		ll ans=0;
		mms(dp,-1);
		FOR(i,k,n)ans=(ans+9*f(i-1,1,0))%P;
		return (int)ans;
	}
};