首页 > Windows开发 > 详细

BZOJ 1026: [SCOI2009]windy数

时间:2015-09-30 01:00:03      阅读:233      评论:0      收藏:0      [点我收藏+]

原题链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1026

题解:

这是个很水的数位dp,令dp[i][j]表示总共i位,第i位是j的方案数。转移就是dp[i][j]+=dp[i-1][k],其中abs(j-k)>=2。然后统计答案的时候瞎比搞搞就好。

代码:

/**************************************************************
    Problem: 1026
    User: HarryGuo2012
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1280 kb
****************************************************************/
 
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cstdio>
#define MAX_N 100
using namespace std;
 
string A,B;
 
typedef long long ll;
 
ll dp[MAX_N][10];
 
ll work(string s) {
    memset(dp, 0, sizeof(dp));
    reverse(s.begin(), s.end());
    int n = s.length();
    for (int i = 0; i < 10; i++)dp[0][i] = 1;
    for (int i = 1; i < n; i++)
        for (int j = 0; j < 10; j++) {
            for (int k = 0; k <= j - 2; k++)
                dp[i][j] += dp[i - 1][k];
            for (int k = j + 2; k <= 9; k++)
                dp[i][j] += dp[i - 1][k];
        }
    ll ans = 0;
    for (int i = 0; i < n - 1; i++)
        for (int j = 1; j <= 9; j++)ans += dp[i][j];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = (i == n - 1); j < s[i] - 0; j++) {
            if ((i != n - 1) && abs(j - s[i + 1] + 0) < 2)continue;
            ans += dp[i][j];
        }
        if ((i != n - 1) && abs(s[i] - s[i + 1]) < 2)break;
    }
    return ans;
}
 
bool check(string s){
    for(int i=1;i<s.length();i++)if(abs(s[i]-s[i-1])<2)return false;
    return true;
}
 
int main() {
    cin >> A >> B;
    cout << work(B) - work(A) + (check(A) && check(B)) << endl;
    return 0;
}

 

BZOJ 1026: [SCOI2009]windy数

原文:http://www.cnblogs.com/HarryGuo2012/p/4847673.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!