程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdu3709 Balanced Number 數位dp

hdu3709 Balanced Number 數位dp

編輯：關於C++

題意：定義一個數為“balanced number” 當其滿足存在一個數位pos(平衡點),在pos左邊的數位的值乘與pos位的距離值的總和等於右

邊的數位的值乘與pos位的距離值的總和，給定一個區間[l , r]，求區間內有多少個balanced number。

思路：設dp[ pos ][ i ][ j ]表示平衡點在i位的情況下，當前考慮pos位，之前已形成的力矩為j(數乘以距離平衡點的距離，在平衡點左

邊的為正，右邊的為負)，之後(pos + 1)位於之前位組合使最後平衡(力矩為0)的數的個數，詳見代碼：

/*********************************************************
  file name: hdu3709.cpp
  author : kereo
  create time:  2015年01月24日 星期六 15時27分47秒
*********************************************************/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int sigma_size=26;
const int N=20;
const int MAXN=1500+50;
const int inf=0x3fffffff;
const double eps=1e-8;
const int mod=100000000+7;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define PII pair
#define mk(x,y) make_pair((x),(y))
int bit[N]; 
ll dp[N][N][MAXN]; //dp[pos][i][j]表示在平衡點為i的情況下，當前考慮pos位，之前已形成的力矩為j，之後(pos+1)位與之前位組合使最後平衡的個數
ll dfs(int pos,int o,int st,int flag){
    if(pos == -1) return st == 0;
    if(flag && dp[pos][o][st]!=-1)
        return dp[pos][o][st];
    int x=flag ? 9 : bit[pos];
    ll ans=0;
    for(int i=0;i<=x;i++){
        int nst=st+(pos-o)*i;
        if(nst<0) //力矩為負直接continue
            continue;
        ans+=dfs(pos-1,o,nst,flag || i