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

hdu 4734 F(x) (數位dp)

編輯:C++入門知識

F(x)

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1140 Accepted Submission(s): 459

Problem Description For a decimal number x with n digits (AnAn-1An-2 ... A2A1), we define its weight as F(x) = An * 2n-1 + An-1 * 2n-2 + ... + A2 * 2 + A1 * 1. Now you are given two numbers A and B, please calculate how many numbers are there between 0 and B, inclusive, whose weight is no more than F(A).
Input The first line has a number T (T <= 10000) , indicating the number of test cases.
For each test case, there are two numbers A and B (0 <= A,B < 109)
Output For every case,you should output "Case #t: " at first, without quotes. The t is the case number starting from 1. Then output the answer.
Sample Input
3
0 100
1 10
5 100

Sample Output
Case #1: 1
Case #2: 2
Case #3: 13

Source 2013 ACM/ICPC Asia Regional Chengdu Online
題意: 看懂f(x)函數之後,求[0,B]內的f(x)的值小於f(a)的有多少個。
思路: 數位dp,由於f(x)的值不大,可以考慮把f(x)放入狀態中。 dp[i][j][k] - i 位 j 開頭f(x)值為k的數的個數。 那麼有dp[i][j][k]=dp[i-1][p][k-j*2^(i-1)] 。 然後算一個區間內的個數時,一位一位往下算就夠了。 考慮到時間的原因,采用了一個sum數組紀錄前綴和。
代碼:
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 10005
#define MAXN 100005
#define mod 100000000
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;

int n,m,ans,cnt,tot,flag;
int a,b,fac[10];
int dp[10][10][5500],sum[10][10][5500];

void solve()
{
    int i,j,t=0,u,v;
    for(i=9;i>=1;i--)
    {
        t+=((a/fac[i-1])%10)*(1<=1;i--)
    {
        u=(b/fac[i-1])%10;
        for(j=0;j=0) t+=dp[i-1][p][k-(1<0) sum[i][j][k]=sum[i][j][k-1]+t;
                else sum[i][j][k]=t;
            }
        }
    }
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&a,&b);
        solve();
        printf("Case #%d: %d\n",++test,ans);
    }
    return 0;
}
/*
3
0 100
1 10
5 100
Case #1: 1
Case #2: 2
Case #3: 13
*/






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