题解 | #小葱的01串#

小䓤的一个数字

大意：给定一个长度为 n （n<=3000）的01字符串s，和整数序列 a , 两种操作:

操作1：每次将字符串中一个字符0变1，1变0.花费为$a_{i}a\_i$

操作2：整体向右平移1位，最左边补字符0, 花费为 b

求将全0的字符串变成 s 的最小花费

思路：如果不考虑操作2，显然是很简单的，直接算就行了。有了操作2，假设用了 k次操作2，那么对于某一个位置 i ,我们可以把 [i-k,i] 的任意一个位置变成 1，通过不超过k次操作2变成最终的s，也就是区间最小值问题 。n 范围不大，直接暴力预处理就行了。

代码如下：

#include <bits/stdc++.h>
#define int long long 
#define rep(i,bbb,eee) for(int i=bbb;i<=eee;i++)
#define frep(i,bbb,eee) for(int i=bbb;i>=eee;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define pb push_back
#define AC signed
// #define x first
// #define y second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const int N=3010,M=1000000007;
int n,a[N],m,f[N][N];
char s[N];
void solve()
{
	cin>>n;
	rep(i,1,n)cin>>a[i],f[i][i]=a[i];
	cin>>m>>(s+1);
	rep(i,1,n)
		rep(j,i+1,n)
			f[i][j]=min(a[j],f[i][j-1]);

	int ans=1e18;
	rep(k,0,n-1)
	{
		int tmp=0;
		rep(i,1,n)
		{
			if(s[i]=='1')
				tmp+=f[max(1LL,i-k)][i];
		}
		ans=min(ans,tmp+m*k);
	}
	cout<<ans<<"\n";
}
AC main()
{
	ios::sync_with_stdio(false);cin.tie(0);
	int _=1;
	//cin>>_;
	while(_--)solve();
	return 0;
}