Codeforces_B.Maximum Sum of Digits

http://codeforces.com/contest/1060/problem/B

题意：将n拆为a和b，让a+b=n且S(a)+S(b)最大，求最大的S(a)+S(b)。

思路：考虑任意一个数，例如156，将其分为 d1:（1，155）或 d2:（6，150），其实S(a)+S(b)都是；但是当分为 d3:（7，149）或 d4:（9，147）时（此时，由d2变为d3，b的个位由0变为9，跨越0），S(a)+S(b)变为了；将其分为 d5:（57，99）或 d6:（68，88）时，S(a)+S(b)变为。S(a)+S(b)是如何变大的？考虑b任意一个数位，当其从0变为9，S(a)增大1，S(B)增大8；当是其它情况时（数位变化不跨越0），相当于S(a)+x, S(b)-x，S(a)+S(b)不变。总结起来，划分（a，b）时让尽量多的数位变化能够跨越0，等于让b的每一位尽量分最多出来。得到贪心策略，每一数位都分9出来。例如，对4394826划分为（999999，3394827）

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

#define LL long long

int digitsum(LL x)

{

    int res=;

    while(x>)

    {

        res+=x%;

        x/=;

    }

    return res;

}

int main()

{

    LL n;

    while(scanf("%I64d",&n)!=EOF)

    {

        int cnt9=;

        LL tmp9=;

        while(tmp9<=n)

        {

            tmp9=tmp9*+;

            cnt9++;

        }

        tmp9/=;

        cnt9--;

        int res=cnt9*+digitsum(n-tmp9);

        printf("%d\n",res);

    }

    return ;

}