description

 
<tt>
有一个长度为n，由数字[0,9]组成的串。我们至多对其进行一次操作，
该操作选定一个区间，将区间内的数 改成 s[i] = (10-s[i])%10  (l&lt;=ii&lt;=r);
求s[0]+s[1]+……+s[n-1] 的最大值。
</tt>

input

 
<tt>
输入一个n (1&lt;=n&lt;=1000 000) 表示这个字符串的长度,下一行输入一个长度为n
的由0~9组成的字符串
</tt>

output

 
<tt>
输出这个最大值</tt>

sample_input

 
<tt>
3
912
3
999
10
3775053808
10
2580294019
10
4701956095
</tt>

sample_output

 
<tt>
26
27
50
50
54
</tt>

hint

 
<tt>
3
912 我们对区间[1,2]进行操作 得到998  ans = 9 + 9 +8 =26
3
999 我们不进行操作 ans = 9+9+9 = 27;</tt>

简单的小dp

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char a[1000005];
int b[1000005];
int dp[1000005];
int main()
{
    int n;
    int sum;
    while(~scanf("%d",&n))
    {
         scanf("%s",a);
         sum=0;
         for(int i=0;i<n;i++) sum+=a[i]-'0';
         int ans=-9999999;
         memset(dp,0,sizeof(dp));
         for(int i=0;i<n;i++)
         {
              b[i]=(10-a[i]+'0')%10-a[i]+'0';
         }
         dp[0]=max(0,b[0]);
         ans=max(0,dp[0]);
         for(int i=0;i<n;i++)
         {
              dp[i]=max(dp[i-1]+b[i],dp[i]);
              ans=max(dp[i],ans);
         }
         printf("%d\n",ans+sum);
    }
    return 0;
}