2474: 小明的灯
题目描述
小明有 nn 盏灯,初始有些是开的，有些是关的，作为一个节约的孩子，他想关掉所有的灯。但是开关灯需要一些条件,他可以改变ii号灯的状态(将灯打开或将灯关闭)当且仅当 i+1i+1 是亮的且 i+2,i+3...ni+2,i+3...n 号灯是暗的,第 nn 盏灯可以随意开关
改变一盏灯的状态视为一次操作，小明想知道问将所有灯变暗最少需要多少次操作
输入
输出
样例输入 复制
样例一：
11011
样例二：
1001样例输出 复制
样例一：
18
样例二：
14提示
对于 10\%10%的数据，输入全为00
另有 20\%20%的数据，输入只有第一个字符是11
另有 20\%20%的数据，输入全是11
另有 20\%20%的数据，n \leq 10n≤10
对于100\%100%的数据，保证n \leq 50n≤50
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int maxn=60;
char str[maxn];
bool a[maxn];
ll dp[maxn][2];
ll mi[maxn];
ll n;
void init()
{
mi[0]=1;
for(int i=1;i<=n;i++)
mi[i]=mi[i-1]*2;
}
int main()
{
//freopen("light.in","r",stdin);
//freopen("light.out","w",stdout);
cin>>str;
n=strlen(str);
for(int i=0;i<n;i++)
a[i+1]=str[i]-'0';
dp[n][a[n]]=0,dp[n][!a[n]]=1;
init();
// print();
for(int i=n-1;i>=1;i--)
{
dp[i][a[i]]=dp[i+1][0];
dp[i][!a[i]]=dp[i+1][1]+mi[n-i];
}
printf("%lld",dp[1][0]);
return 0;
}