题面
1. 密钥
题目ID：20443
最新提交：
Wrong Answer 40 分
历史最高：
Wrong Answer 40 分
时间限制: 1000ms
空间限制: 524288kB
输入文件名: key.in
输出文件名: key.out
题目描述
在一个大型数据加密系统中，当前的密钥序列 a 已经老化，需要更新为一个新的安全密钥序列 b。为了确保数据的安全性，工程师们必须逐步将密钥序列 a 变换为目标密钥序列 b。密钥序列仅包含0和1。
每次变换时，工程师可以修改密钥序列中的某个字符，将其从0变成1或者从1变成0。但由于系统老化，工程师需同时维护密钥中剩余的字符。如果变换后第ii位的字符为1，那么它会给这次变换带来 c_i 的维护成本。因此可以认为每一次变换的维护成本为 \Sigma_{i\in S}c_i ，其中S为所有变换后为1的位置。
工程师们想要知道将密钥从 a 变成 b 的最小维护成本。
输入格式
从文件key.in 中读入数据。
数据第一行包含一个整数n，表示密钥的长度。
接下里的一行包含n个正整数，表示第i个位置为1时的维护成本 c_i 。
第三行包含一个长度为n的字符串a,保证仅包含1和0。
第四行包含一个长度为n的字符串b,保证仅包含1和0。
输出格式
输出文件导key.out中。
输出一行包含一个整数表示最小维护成本。
样例
Input 1
5 8
19 6 11 17
01011
11000
Output 1
74
Input 2
7 6
20 19 12 10 10 15
1101010
0110101
Output 2
193
对于所有数据，保证 n\leq5×10^3,c_i\leq10^9 。
思路
若两个串中都为0，则无需对该位做任何操作；
若由1–>0，0–>1则都只需最多做一次操作；
其中，显然是先让权值大的1–>0先操作，
将1–>0的操作完后，再让权值小的0–>1的操作。
看完上面这些是不是感觉很简单？
那开始写吧————WA20
这是因为当两个串都为1时
有两种可能:
1.不动
显然这是一种可行的方案
如：
111111110–>111111111
2.1-->0-->1
样例中两个也都用到了该方案
以样例1为例：
01011–>00011–>00010–>00000–>10000–>11000
那么现在最重要的问题就是：
遇到(1,1)的情况时，什么时候用1方案，什么时候用2方案
代码
#include<bits/stdc++.h>//头文件
#define L long long//定义long long
using namespace std;//命名空间
struct Key{//结构体
L id,val;//定义id:编号,和val:权值
}on[5005],of[5005];//定义on:从0变1,和of:从1变0
string s1,s2;//定义s1和s2
L n,cnt_on,cnt_of,ans,sum,cnt,c[5005];//定义n:灯的数量(将0,1串看为灯的亮与灭),cnt_on:从0变1的数量,cnt_of:从1变0的数量,ans:答案,sum:当前权值和,cnt:当前灯的数量,c:灯的权值
bool vis[5005],flag[5005];//定义vis:灯是否被按下过
bool cmp1(Key a,Key b){return a.val>b.val;}//定义cmp1:从大到小排序
bool cmp2(Key a,Key b){return a.val<b.val;}//定义cmp2:从小到大排序
bool check(int x){//判断在1,1情况下是否可以按下
sum=0;cnt=0;//初始化
for(int i=x+1;i<cnt_of;i++){//从x+1开始
sum+=of[i].val;//累加权值
cnt++;//累加灯的数量
}
for(int i=0;i<cnt_on;i++){//从0开始
if(on[i].id==of[x].id)break;//如果当前灯的编号等于x的编号,跳出循环
else{//否则
cnt++;//累加灯的数量
sum+=on[i].val;//累加权值
}
}
if(sum<((cnt-1)*of[x].val))return 1;//如果权值和小于当前灯的权值,返回正确
else return 0;//否则返回错误
}
void OFF(){//从1变0
for(int i=0;i<cnt_of;i++){//从0开始
if(vis[of[i].id]){//在1,1情况下
if(check(i)){//判断是否可以按下
flag[of[i].id]=1;//标记当前灯被按下过
s1[of[i].id]='0';//将当前灯的编号变为0
for(int j=0;j<n;j++)if(s1[j]=='1')ans+=c[j];//累加权值
}else continue;//否则继续
}else{//否则
s1[of[i].id]='0';//将当前灯的编号变为0
for(int j=0;j<n;j++)if(s1[j]=='1')ans+=c[j];//累加权值
}
}
return ;
}
void ON(){//从0变1
for(int i=0;i<cnt_on;i++){//从0开始
if(s1[on[i].id]=='1')continue;//如果当前灯的编号为1,继续
s1[on[i].id]='1';//将当前灯的编号变为1
for(int j=0;j<n;j++)if(s1[j]=='1')ans+=c[j];//累加权值
}
return ;
}
int main(){
freopen("key.in","r",stdin);
freopen("key.out","w",stdout);
scanf("%lld",&n);//输入n
for(int i=0;i<n;i++)scanf("%lld",&c[i]);//输入c
cin>>s1>>s2;//输入s1和s2
for(int i=0;i<n;i++){//从0开始
if(s1[i]=='1' && s2[i]=='1'){//如果当前灯的编号为1,1
of[cnt_of++]={i,c[i]};
on[cnt_on++]={i,c[i]};
vis[i]=1;//标记当前灯为1,1状态
}
else if(s1[i]=='1' && s2[i]=='0')of[cnt_of++]={i,c[i]};//如果当前灯的编号为1,0
else if(s1[i]=='0' && s2[i]=='1')on[cnt_on++]={i,c[i]};//如果当前灯的编号为0,1
}
sort(of,of+cnt_of,cmp1);//从大到小排序
sort(on,on+cnt_on,cmp2);//从小到大排序
OFF();//从1变0
ON();//从0变1
printf("%lld\n",ans);//输出答案
return 0;
}
