51nod1537

题解：

预处理每一个要变换几次，然后改成每一个要改变的次数-上一个要改变的次数

然后对于区间[l,r]修改，就是l++，r+1++

dp即可（据说可以o(n)）

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2523;
int a[N],add[N],Dec[N],pr[N],Aft[N],f[N*9],n,m;
char s[N],t[N];
int read()
{
    char rx=getchar();
    int ra=0;
    for(;rx<'0'&&rx!='-';rx=getchar());
    for(;rx>='0'&&rx<='9';ra=ra*10+rx-48,rx=getchar());
    return ra;
}
int MOD(int x)
{
    return x<0?x+10:x>9?x-10:x;
}
int main()
{
    for(int T=read();T;T--)
     {
        scanf("%s%s",s+1,t+1);
        n=strlen(s+1);
        for(int i=1;i<=n;i++)
         {
             a[i]=MOD(t[i]-s[i]);
             add[i]=MOD(a[i]-a[i-1]);
             Dec[i]=10-add[i];
             pr[i]=pr[i-1]+add[i];
         }
        for(int i=n;i;i--)
         Aft[i]=Aft[i+1]+Dec[i];        
        memset(f,60,(pr[n]+1)<<2);
        f[0]=0;
        for(int i=1;i<=n;i++)
         if(add[i])
          {
            int tmp=Dec[i],j,k;
            for(j=pr[i],k=j-add[i];k>=0;j--,k--)
             f[j]=min(f[j]+tmp,f[k]);
            while(j>=0)f[j--]+=tmp;
          }
        int ans=1e9;
        for(int i=0;i<=pr[n]&&i<ans;i++)
         ans=min(ans,max(i,f[i]));
        printf("%d
",ans);
     }
}