cf 2000+()-其他

cf 2000+()

D2. Zero-One (Hard Version) 2000 好dp

https://codeforces.com/problemset/problem/1733/D2

1，当x>=y时

2，x<y时，

f(0,i,j)=min(f(0,i-1,j),f(1,i-1,j));
f(1,i,j)=min(f(0,i-1,j)+y,f(1,i,j)+x,f(0,i-1,j-2)+x,f(1,i-1,j-2)+y)

f(1,i,j)=min(f(1,i-1,j-1),f(0,i-1.j-1));
f(0,i,j)=min(f(1,i-1,j+1)+x,f(0,i-1,j+1)+y,f(0,i-1,j-1)+x,f(1,i-1,j-1)+y)

``````#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5050,mod=998244353;
int a[N],b[N],c[N],f0[N][N],f1[N][N];

void solve(){
int n,x,y;cin>>n>>x>>y;
string s;cin>>s;
for(int i=0;i<n;i++) a[i+1]=s[i]-'0';
cin>>s;
for(int i=0;i<n;i++) b[i+1]=s[i]-'0';
int cnt=0;
for(int i=1;i<=n;i++) c[i]=a[i]^b[i],cnt+=c[i];
if(cnt%2){
puts("-1");
return;
}
if(x>=y){
if(cnt==2){
int q=0,w=0;
for(int i=1;i<=n;i++){
if(c[i]==1)
if(!q) q=i;
else w=i;
}
if(abs(q-w)!=1){
cout<<y<<endl;
}
else{
if(n<=3){
cout<<x<<endl;
}
else if(n==4){
if(q==1||w==n){
cout<<min(2*y,x)<<endl;
}
else cout<<min(3*y,x)<<endl;
}
else{
cout<<min(x,2*y)<<endl;
}
}
return;
}
cout<<cnt/2*y<<endl;
return;
}
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++) f0[i][j]=f1[i][j]=1e18;
}
if(c[1]==1) f1[1][1]=0;
else f0[1][0]=0;
for(int i=2;i<=n;i++){
for(int j=0;j<=i;j++){
if(c[i]==0){
f0[i][j]=min(f0[i-1][j],f1[i-1][j]);
if(j<=1) f1[i][j]=min(f0[i-1][j]+y,f1[i-1][j]+x);
else{
f1[i][j]=min({f0[i-1][j]+y,f1[i-1][j]+x,f0[i-1][j-2]+x,f1[i-1][j-2]+y});
}
}
else{
if(j!=0)
f1[i][j]=min(f1[i-1][j-1],f0[i-1][j-1]);
if(j==0){
f0[i][j]=min(f0[i-1][j+1]+y,f1[i-1][j+1]+x);
}
else if(j==i){
f0[i][j]=min(f0[i-1][j-1]+x,f1[i-1][j-1]+y);
}
else{
f0[i][j]=min({f0[i-1][j+1]+y,f1[i-1][j+1]+x,f0[i-1][j-1]+x,f1[i-1][j-1]+y});
}
}
}
}
cout<<f0[n][0]<<endl;
}
signed main(){
int T;cin>>T;
while(T--) solve();
}
``````

C2. Sheikh (Hard Version) 2100

https://codeforces.com/problemset/problem/1732/C2

————————

D2. Zero-One (Hard Version) 2000 好dp

https://codeforces.com/problemset/problem/1733/D2

1，当x>=y时

2，x<y时，

f(0,i,j)=min(f(0,i-1,j),f(1,i-1,j));
f(1,i,j)=min(f(0,i-1,j)+y,f(1,i,j)+x,f(0,i-1,j-2)+x,f(1,i-1,j-2)+y)

f(1,i,j)=min(f(1,i-1,j-1),f(0,i-1.j-1));
f(0,i,j)=min(f(1,i-1,j+1)+x,f(0,i-1,j+1)+y,f(0,i-1,j-1)+x,f(1,i-1,j-1)+y)

``````#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5050,mod=998244353;
int a[N],b[N],c[N],f0[N][N],f1[N][N];

void solve(){
int n,x,y;cin>>n>>x>>y;
string s;cin>>s;
for(int i=0;i<n;i++) a[i+1]=s[i]-'0';
cin>>s;
for(int i=0;i<n;i++) b[i+1]=s[i]-'0';
int cnt=0;
for(int i=1;i<=n;i++) c[i]=a[i]^b[i],cnt+=c[i];
if(cnt%2){
puts("-1");
return;
}
if(x>=y){
if(cnt==2){
int q=0,w=0;
for(int i=1;i<=n;i++){
if(c[i]==1)
if(!q) q=i;
else w=i;
}
if(abs(q-w)!=1){
cout<<y<<endl;
}
else{
if(n<=3){
cout<<x<<endl;
}
else if(n==4){
if(q==1||w==n){
cout<<min(2*y,x)<<endl;
}
else cout<<min(3*y,x)<<endl;
}
else{
cout<<min(x,2*y)<<endl;
}
}
return;
}
cout<<cnt/2*y<<endl;
return;
}
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++) f0[i][j]=f1[i][j]=1e18;
}
if(c[1]==1) f1[1][1]=0;
else f0[1][0]=0;
for(int i=2;i<=n;i++){
for(int j=0;j<=i;j++){
if(c[i]==0){
f0[i][j]=min(f0[i-1][j],f1[i-1][j]);
if(j<=1) f1[i][j]=min(f0[i-1][j]+y,f1[i-1][j]+x);
else{
f1[i][j]=min({f0[i-1][j]+y,f1[i-1][j]+x,f0[i-1][j-2]+x,f1[i-1][j-2]+y});
}
}
else{
if(j!=0)
f1[i][j]=min(f1[i-1][j-1],f0[i-1][j-1]);
if(j==0){
f0[i][j]=min(f0[i-1][j+1]+y,f1[i-1][j+1]+x);
}
else if(j==i){
f0[i][j]=min(f0[i-1][j-1]+x,f1[i-1][j-1]+y);
}
else{
f0[i][j]=min({f0[i-1][j+1]+y,f1[i-1][j+1]+x,f0[i-1][j-1]+x,f1[i-1][j-1]+y});
}
}
}
}
cout<<f0[n][0]<<endl;
}
signed main(){
int T;cin>>T;
while(T--) solve();
}
``````

C2. Sheikh (Hard Version) 2100

https://codeforces.com/problemset/problem/1732/C2