操作之后每个数前面不是+就是-, 很容易想到0/1背包。但是不是每个数字前面任意填+/-都有对应的操作方案呢?
不是的随便+/-都行的,但是从前往后扫描,如果一个数字前面有两个数字,我们可以任意改变他的+/-而不影响其他数字的符号
-
a[1] 无论如何都不能 -a[1], a[1]前面没有两个数字
-
a[2] 无论如何都不能 +a[2], 因为a[2]前面只有一个数字a[1],a[2]只能而且必须“被减”一次, a[2]前面没有两个数字
- a[3] 前面有两个数字{a[1],a[2]},那么+/-a[3]都可以:
很容易知道, 不论+/-a[3]都可以找到仅在{a[1],a[2],a[3]}上的操作满足a[3]的符号
如果 a[3] 是+, 那么操作 2 : a[2]-a[3]
{a[1]* ,a[2]*} = {a[1], a[2]-a[3]}
如果 a[3] 是-, 那么操作 1 : a[1]-a[2]
{a[1]* ,a[2]*} = {a[1]-a[2], a[3]} -
a[4] 前面有两个数字{a[1]*,a[2]*},那么+/-a[4]都可以:
很容易知道, 不论+/-a[4]都可以找到仅在{a[1]*,a[2]*,a[4]}上的操作满足a[4]的符号
如果 a[4] 是+, 那么操作 2 : a[2]*-a[4]
{a[1]* ,a[2]*} = {a[1]*, a[2]*-a[4]}
如果 a[4] 是-, 那么操作 1 : a[1]*-a[2]*
{a[1]* ,a[2]*} = {a[1]*-a[2]*, a[4]} -
…
- a[i] 前面有两个数字{a[1]*,a[2]*},那么+/-a[i]都可以:
很容易知道, 不论+/-a[i]都可以找到仅在{a[1]*,a[2]*,a[i]}上的操作满足a[i]的符号
如果 a[i] 是+, 那么操作 2 : a[2]*-a[i]
{a[1]* ,a[2]*} = {a[1]*, a[2]*-a[i]}
如果 a[i] 是-, 那么操作 1 : a[1]*-a[2]*
{a[1]* ,a[2]*} = {a[1]*-a[2]*, a[i]}
最后我们再进行一次a[1]* - a[2]*操作.
我们发现我们只进行了, 1, 2操作
#include <bits/stdc++.h>
using namespace std;
const int N = 102, V = 10002;
int n, t, a[N], s, v;
bool f[N][V];
int main()
{
cin >> n >> t;
s = 0;
int x, y;
cin >> x >> y;
int pre = x - y;
for (int i = 3; i <= n; i++)
{
cin >> a[i];
s+= a[i];
}
v = (s + pre -t)>>1;
for (int i = 3; i <= n; i++)
{
f[i-1][0] = 1;
for (int j = v; j >= a[i]; j--)
{
f[i][j] = f[i-1][j] || f[i-1][j - a[i]];
}
}
int value = v;
unordered_set<int> ans;
for (int i = n; i ; i--)
{
if (f[i][value] && !f[i-1][value])
{
ans.insert(i);
value-= a[i];
if (!value) break;
}
}
for (int i = 3; i <= n; i++)
{
if (ans.count(i))
{
// negative
cout << 1 << endl;
} else
{
cout << 2 << endl;
}
}
cout << 1 << endl;
}