http://acm.timus.ru/problem.aspx?space=1&num=1830
這道題需要理解題目操作的意思,
要更改第i位的狀態,第i-1位必須激活為1,0-i-2位必須為0,如果0-i-1位開始時全為0,那么從0位開始進行操作
一.首先考慮對于0-i-1位都是0,需要更改i位的情況,需要 1.更改i-1位,2.按一下打開下一頁
對于更改i-1位,需要1.更改i-2位,2.按一下打開下一頁,3.更改i-2位
可以得到一個式子,設f[i]為第0-i-1位均為0時,使得狀態成為第i位被更改,第0-i-1位仍為0的操作數,則f[i]=2*f[i-1]+1
二.因為從前往后更改會影響之前的狀態,所以我們從后往前更改,當最后一個不相同位置e已被上面的操作更改后,只有e-1位為1,其它都為0,滿足上面的條件,可以直接相加
三.對于更改最后一位e的操作,因為這個時候前面不一定全都為0,所以有:
假設第e位是第i個1,
對于第i-1個1,這個1是有用的,可以作為起點,如果它是第j位,它的操作數為f[j]+1,對于e來說,因為計算f[e]時認為2*f[j]+1,所以要減去f[j],
對于第i-2個1,這個1阻礙了第i-1個1,是無用的,如果它是第j位,它的操作數為3*f[j]+1(一次關閉操作),對于e來說,需要加上f[j]
對于第i-3個1,有用,
對于第i-4個1,無用........
依次類推,直接相加可得答案
四:注意long long
?
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
char org[100],aim[100];
ll f[50];
int main(){int n;ll ans=0;scanf("%d%s%s",&n,org,aim);f[0]=1;for(int i=1;i<n;i++){f[i]=2*f[i-1]+1;}for(int i=n-1;i>=0;i--){if(org[i]==aim[i])continue;ll sub=0;int fl=1;for(int j=i-1;j>=0;j--){if(org[j]=='1'){sub=sub+f[j]*fl;if(j!=i-1)org[j]='0';fl=-fl;}}if(i>0)org[i-1]='1';ans+=(i>0?f[i-1]:0)-sub+1;org[i]=aim[i];}printf("%I64d\n",ans);return 0;
}
)
