程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4389 X mod f(x) (數位DP)

HDU 4389 X mod f(x) (數位DP)

編輯:C++入門知識

HDU 4389 X mod f(x) (數位DP)


 
第一次遇到需要先枚舉然後再數位DP的。
先枚舉各位數之和,即,1~81,然後數位DP過程中再判斷枚舉的各位數之和與枚舉的數是否相同,只有相同的才算。
dp[i][j][k][h]表示第i位上,當前的各位數和為j,枚舉的各位數和為k,當前的數對k取模為h的數的個數。
代碼如下:

#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
using namespace std;
#define LL __int64
#define pi acos(-1.0)
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
const int MAXN=200000+10;
int dp[11][82][82][82], dig[11];
int dfs(int cnt, int sum, int mods, int res, int maxd)
{
        if(cnt==-1) return sum==mods&&res==0;
        if(sum>mods) return 0;
        if(maxd&&dp[cnt][sum][mods][res]!=-1) return dp[cnt][sum][mods][res];
        int i, r=maxd?9:dig[cnt], ans=0;
        for(i=0;i<=r;i++){
                ans+=dfs(cnt-1,sum+i,mods,(res*10+i)%mods,maxd||i

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved