[51nod1357]密码锁暨 GDOI2018d1t2

　　有一个密码锁，其有N位，每一位可以是一个0~9的数字，开启密码锁需要将锁上每一位数字转到解锁密码一致。这个类似你旅行用的行李箱上的密码锁，密码锁的每一位其实是一个圆形转盘，上面依次标了0,1，...9,对每一位来说可以正向或者逆向拨动，正向拨动时原有数字x会变成新的数字(x+1 mod 10),例如1->2，2->3，9->0；同理逆向拨动变为(x-1 mod 10)即9->8,5->4,0->9。定义对密码锁的一次操作：选择一个连续的区间[L,R]，可以只包含一位即L==R，将这个区间的所有数字正向拨动或逆向拨动一次，注意要么全部正着拨，要么全逆着。例如：12397正向后变成23408，逆向后变成01286。给出密码锁初始和解锁需要的终止状态，问最少多少次操作能解锁。
　Input
　　多组测试数据，第一行一个整数T，表示测试数据数量，1<=T<=5
　　每组测试数据有相同的结构构成：
　　每组数据有两行构成，第一行是密码锁的初始状态S，第二行是解锁的终止状态E，其中1<=len(S)=len(E)<=2500,且都由0~9构成
　Output
　　每组数据一行输出，即最少需要的操作数。

简化分析，先对每一位重映射，目标转化为第i位需要正转L次变成目标位。简单的说就是把目标串变成'0000....000000000'。
第二次转化，因为目标是把所有的位置0，所以我们定义NewBit[i] = (Bit[i]-Bit[i-1]) mod 10;NewBit[0]=Bit[0]
Bit[]={0,0,0,.....,0}等价NewBit[]={0,0,.........,0}，两个问题等价

对Bit[]的[L,R]区间整体位移，等价为对NewBit[]中NewBit[L]与NewBit[R]两个量操作，一个+1，一个-1.其中R=N-1时，没有R+1这项，只有NewBit[L]自己动。一次影响两个项，很容易想到贪心，每个NewBit[]只网一个方向变，即将一些项往正方向转，一些往负方向转，他们两类可以配对，若正的比负的多，用多出来的与R=N配对即可。

在NewBit[]中做一个简单N^2dp背包即可以求解。

具体DP的话就是f[i][j]表示处理完前i个数，正转操作的数量为j时，负方向最少要转多少次。

看了别人的AC代码其实也可以不用DP的样子...每次拿需要正转次数最多和需要负转次数最多的去强行配对似乎就行了？

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 #include<cmath>
 7 #include<cstdlib>
 8 #define ll long long
 9 #define ull unsigned long long
10 #define ui unsigned int
11 #define d double
12 #define ld long double
13 const int maxn=2523,modd=1000000007;
14 
15 int a[maxn],add[maxn],dec[maxn],pr[maxn],aft[maxn],f[maxn*9];
16 int i,j,k,n,m;
17 char s[maxn],t[maxn];
18 
19 int ra,fh;char rx;
20 inline int read(){
21     rx=getchar(),ra=0,fh=1;
22     while(rx<'0'&&rx!='-')rx=getchar();
23     if(rx=='-')fh=-1,rx=getchar();
24     while(rx>='0')ra=ra*10+rx-48,rx=getchar();return ra*fh;
25 }
26 
27 inline int min(int a,int b){return a<b?a:b;}
28 inline int max(int a,int b){return a>b?a:b;}
29 inline void mins(int &a,int b){if(b<a)a=b;}
30 inline int MOD(int x){return x<0?x+10:x>9?x-10:x;}
31 int main(){
32     for(int T=read();T;T--){
33         scanf("%s%s",s+1,t+1);n=strlen(s+1);int tmp;
34         for(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];
35         for(i=n,aft[n+1]=0;i;i--)aft[i]=aft[i+1]+dec[i];
36         
37     //    for(i=1;i<=n;i++)printf(" %d",a[i]);puts("");
38         
39         memset(f,60,(pr[n]+1)<<2);
40         f[0]=0;
41         for(i=1;i<=n;i++)if(add[i]){
42             tmp=dec[i];
43             for(j=pr[i],k=j-add[i];k>=0;j--,k--)
44                 mins(f[j]+=tmp,f[k]);
45             while(j>=0)f[j--]+=tmp;
46         }
47         int ans=1e9;
48         for(i=0;i<=pr[n]&&i<ans;i++)mins(ans,max(i,f[i]));
49         printf("%d
",ans);
50     }
51 }

View Code

2018.4 UPD: 达成成就：2016年(嘴巴上)A掉GDOI2018的题目。

[51nod1357]密码锁 暨 GDOI2018d1t2

[51nod1357]密码锁暨 GDOI2018d1t2