求助蚂蚁笔试第二题,我这样写为啥不对呀
有一个01字符串,每个字符都有一个价值,字符串中不能出现 110,问删除一定字符后最大价值是多少
#include
using namespace std;
const int N = 2e5 + 10;
typedef long long LL;
LL a[N];
LL f[N][3];
int main()
{
int n; cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
string s; cin >> s; s = " " + s;
for (int i = 1; i <= n; i ++)
{
char c = s[i];
if (c == '0')
{
f[i][1] = f[i - 1][1];
f[i][2] = f[i - 1][2];
f[i][0] = max(f[i - 1][0], f[i - 1][1]) + a[i];
}
else
{
f[i][0] = f[i - 1][0];
f[i][1] = f[i - 1][0] + a[i];
f[i][2] = max(f[i - 1][1], f[i - 1][2]) + a[i];
}
}
cout << max(f[n][0], max(f[n][1], f[n][2]));
}
#include
using namespace std;
const int N = 2e5 + 10;
typedef long long LL;
LL a[N];
LL f[N][3];
int main()
{
int n; cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
string s; cin >> s; s = " " + s;
for (int i = 1; i <= n; i ++)
{
char c = s[i];
if (c == '0')
{
f[i][1] = f[i - 1][1];
f[i][2] = f[i - 1][2];
f[i][0] = max(f[i - 1][0], f[i - 1][1]) + a[i];
}
else
{
f[i][0] = f[i - 1][0];
f[i][1] = f[i - 1][0] + a[i];
f[i][2] = max(f[i - 1][1], f[i - 1][2]) + a[i];
}
}
cout << max(f[n][0], max(f[n][1], f[n][2]));
}
全部评论
兄弟问一下,你还记得最后一题那个翻转是对节点本身翻转,还是对节点子树或者其他的什么东西翻转不
c==1的情况,f[i][1] = max(f[i-1][0]+a[i], f[i-1][1])
相关推荐
查看25道真题和解析
海康威视公司福利 1125人发布