NOIP专题复习——专题二:动态规划基础

时间:2021-12-07 18:43:54

15个题,希望对大家有帮助,欢迎指出错误,交流算法。

数字三角形W

题目来源:【CodeVS 2189】

题意:

数字三角形,变为对100取模后的最大值。

思路:

当一种状态的影响不可忽略的时候,就加到动态规划当中,就是再加上一维。
dp[i][j][k] 表示,第i行的第j个,当余数是否能为k。
状态转移方程:
dp[i][j][k]=dp[i1][j][(((kv[i][j])%p)+p)%p] || dp[i1][j1][(((kv[i][j])%p)+p)%p]

代码:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int p = 100;
int n, mx;
int v[30][30];
bool f[30][30][110];
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= i; j ++)
scanf("%d", &v[i][j]);
f[1][1][((v[1][1]%p)+p)%p] = 1;
for(int i = 2; i <= n; i ++)
for(int j = 1; j <= i; j ++)
for(int k = 0; k <= 99; k ++)
f[i][j][k] = f[i-1][j][((k-v[i][j])%p+p)%p]
|| f[i-1][j-1][((k-v[i][j])%p+p)%p];
for(int i = 1; i <= n; i ++)
for(int j = 99; j >= 0; j --)
if(f[n][i][j]){mx = max(mx, j);break;}
printf("%d", mx);
return 0;
}

花店橱窗布置

题目来源:【洛谷 1854】

题意:

给定一个 nm 的矩阵 A(nm) ,求一个序列 a1,a2,a3,...,an 满足 1a1<a2<a3<...<anm 使得 A[1][a1]+A[2][a2]+...+A[n][an] 最大。

思路:

考虑转换为背包问题。
dp[i][j] 表示现在处理到第i行,第i行选第j个,可以得到的最大值。
状态转移方程: dp[i][j]=max{dp[i1][k]}+A[i][j](1k<j)
注意处理好边界条件,因为有负值,所以要把dp数组初始化为负无穷。

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf = 1e9;
int v[110][110], f[110][110], pre[110][110], mx, mx_num;
int res[110], ct;
int main(){
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i <= n; i ++)
for(int j = 0; j <= m; j ++)
f[i][j] = -inf;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
scanf("%d", &v[i][j]);
for(int i = 1; i <= m; i ++) f[1][i] = max(v[1][i], f[1][i-1]);
for(int i = 2; i <= n; i ++)
for(int j = i; j <= m-n+i; j ++)
for(int k = i-1; k < j; k ++)
if(f[i][j] < f[i-1][k] + v[i][j])
f[i][j] = f[i-1][k] + v[i][j], pre[i][j] = k;
for(int i = 1; i <= m; i ++)
if(mx < f[n][i]) mx = f[n][i], mx_num = i;
ct = n;
printf("%d\n", mx);
for(int i = mx_num; i; i = pre[ct--][i]) res[ct] = i;
for(int i = 1; i <= n; i ++) printf("%d ", res[i]);
return 0;
}

机器分配

题目来源:【洛谷 2066】

题意:

总公司拥有高效设备M台,准备分给下属的N个分公司。各分公司若获得这些设备,可以为国家提供一定的盈利。问:如何分配这M台设备才能使国家得到的盈利最大?求出最大盈利值。其中M≤15,N≤10。分配原则:每个公司有权获得任意数目的设备,但总台数不超过设备数M。

思路:

dp[i][j] 表示前i个店,总共购买j台的最大收益。
状态转移方程: dp[i][j]=min{dp[i1][jk]+a[i][k]}
洛谷的好像没有spj,所以要用 更新才可以过。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int v[20][20], f[20][20], pre[20][20], res[20];
int n, m, mx, ct, mx_num;
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
scanf("%d", &v[i][j]);
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
for(int k = 0; j >= k && k <= m; k ++){
if(f[i][j] <= f[i-1][j-k] + v[i][k]){
f[i][j] = f[i-1][j-k] + v[i][k];
pre[i][j] = j-k;
}
}
}
}
for(int i = 1; i <= n; i ++)
if(mx < f[i][m]) mx = f[i][m];
printf("%d\n", mx);
ct = n;
for(int i = m; i; i = pre[ct--][i]) res[ct] = i;
for(int i = 1; i <= n; i ++) printf("%d %d\n", i, res[i]-res[i-1]);
return 0;
}

烽火传递

题目来源:【Smart OJ 1475】

题意:

给定n个非负整数,选择其中若干个数字,使得每连续k个数中至少有一个被选出。要求选择的数字之和尽可能小。

思路:

dp[i] 表示选第i个数,且满足条件的最小值。
状态转移方程: dp[i]=min{dp[j]}+a[i](ij+1k)
可用单调队列优化。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int v[1000010], f[1000010];
int q[1000010], mn = 1e9;
int main(){
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++) scanf("%d", &v[i]);
int l = 1, r = 0;
f[0] = 0;
for(int i = 1; i <= n; i ++){
while(l <= r && f[q[r]] >= f[i-1]) r --;
q[++r] = i-1;
while(l <= r && i-q[l] > m) l ++;
f[i] = f[q[l]] + v[i];
if(n-i < m) mn = min(f[i], mn);
}
printf("%d", mn);
return 0;
}

传球游戏

题目来源:【洛谷 1057】

题意:

n个人站成一个圈传球,从1号开始传,每次等机率向左或向右传,问传m次以后,传到1号的方案数。

思路:

dp[i][j] 表示第 i 个人,传了 j 次的方案数。
转移方程:
dp[i][j]=dp[i1][j1]+dp[i+1][j1]
注意特判一下 1 n 的情况。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int f[50][50];
int main(){
int n, m;
scanf("%d%d", &n, &m);
f[1][0] = 1;
for(int i = 1; i <= m; i ++){
for(int j = 1; j <= n; j ++){
if(j == 1){
f[1][i] = f[2][i-1] + f[n][i-1];
}else if(j == n){
f[n][i] = f[n-1][i-1] + f[1][i-1];
}else{
f[j][i] = f[j-1][i-1] + f[j+1][i-1];
}
}
}
printf("%d", f[1][m]);
return 0;
}

尼克的任务

题目来源:【洛谷 1280】

题意:

尼克的一个工作日为N分钟,从第一分钟开始到第N分钟结束。当尼克到达单位后他就开始干活。如果在同一时刻有多个任务需要完戍,尼克可以任选其中的一个来做,而其余的则由他的同事完成,反之如果只有一个任务,则该任务必需由尼克去完成,假如某些任务开始时刻尼克正在工作,则这些任务也由尼克的同事完成。如果某任务于第P分钟开始,持续时间为T分钟,则该任务将在第P+T-1分钟结束。计算最大的闲暇时间。

思路:

dp[i] 表示前 i 个分钟的最大闲暇时间。
转移时考虑两种情况:
1. 这一时刻没有任务,则 dp[i]=max(dp[i1],dp[i])
2. 这一时刻有任务,则可以推出以后的闲暇时间,设任务持续到的时间是 t ,那么 dp[t]=max(dp[t],dp[i1])
因为任务是必须有就要做的,所以只有当一个状态只能由任务已经完成的状态推得,休息的条件是这个时间点不在执行任务,即把dp数组初始化为 inf dp[0]=1

代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int inf = 1e9;
vector <int> p[10010];
int f[10010], mx;
int main(){
int n, k;
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i ++) f[i] = -inf;
for(int i = 1; i <= k; i ++){
int a, b;
scanf("%d%d", &a, &b);
p[a].push_back(a+b-1);
}
for(int i = 1; i <= n; i ++){
if(!p[i].size()) f[i] = max(f[i-1] + 1, f[i]);
for(int j = 0; j < p[i].size(); j ++){
f[p[i][j]] = max(f[p[i][j]], f[i-1]);
}
}
printf("%d", f[n]);
return 0;
}

下面就不写题意了,都是中文题。
感觉难点都不在dp,而是在模型的抽象化,收获颇多。


低价购买

题目来源:【洛谷 1108】

思路:

最长下降子序列+方案数。至于第二问求方案数,相同的数字只从靠后面的转移方案。

代码:

#include <cstring>
#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
const int maxn = 5010;
int n, a1[maxn], num[maxn], dp[maxn];
map <int, bool> map1;
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i ++){
scanf("%d", &a1[i]);
}
for(int i = 1, mx1, mx2; i <= n; i ++){
dp[i] = 1;
mx1 = 0; mx2 = 0, map1.clear();
for(int j = i-1; j > 0; j --){
if(a1[j] > a1[i]){
if(dp[j] >= mx1){
if(dp[j] == mx1){
if(map1[a1[j]] == 1) continue;
else map1[a1[j]] = 1, mx2 += num[j];
}else mx1 = dp[j], mx2 = num[j], map1.clear(), map1[a1[j]] = 1;
}
}
}
dp[i] = mx1+1;
num[i] = mx2==0?1:mx2;
}
int max1 = 0, max2 = 0;
map1.clear();
for(int i = n; i >= 1; i --){
if(max1 < dp[i])
max1 = dp[i], max2 = num[i], map1.clear(), map1[a1[i]] = 1;
if(max1 == dp[i]){
if(map1[a1[i]] == 1) continue;
else max2 += num[i], map1[a1[i]] = 1;
}
}
printf("%d %d", max1, max2);
return 0;
}

多米诺骨牌

题目来源:【洛谷 1282】

思路:

dp[i][j] 表示前 i 张骨牌,上下之差为 j 的最小翻转次数,设 Ai,Bi 分别表示第 i 张骨牌上值和下值
状态转移方程:
dp[i][j+(AiBi)]=min(dp[i][j+(AiBi)],dp[i][j])
dp[i][j(AiBi)]=min(dp[i][j(AiBi)],dp[i][j]+1)
要加上一个数,让下标都是正的。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int p = 7000;
int f[1010][14010], ans = 1e9;
int main(){
int n; scanf("%d", &n);
memset(f, 63, sizeof f);
f[0][p] = 0;
for(int i = 0; i < n; i ++){
int a, b, t;
scanf("%d%d", &a, &b);
t = a-b;
for(int j = -6000; j <= 6000; j ++){
f[i+1][j+t+p] = min(f[i+1][j+t+p], f[i][j+p]);
f[i+1][j-t+p] = min(f[i+1][j-t+p], f[i][j+p]+1);
}
}
for(int i = 0; i <= 6000; i ++){
if(f[n][i+p] <= 1000 || f[n][p-i] <= 1000){
ans = min(f[n][i+p], f[n][p-i]);
break;
}
}
printf("%d", ans);
return 0;
}

烹调方案

题目来源:【洛谷 1417】

思路:

一个很好的贪心性质:当制作A食材的时间 × B食材的单位损耗 < 制作B食材的时间 × A食材的单位损耗时,我们一定是优先选择A食材,我们可以把第一项看做先制作A食材对B的影响,第二项看做先制作B食材对A的影响,我们当然先做影响相对较小的,所以先按上面的运算排序,再做背包,选出最优的组合。
典型背包,方程没有什么好说的。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
struct node{
ll num, a, b;
bool operator < (const node &t)const{
return a*t.b > b*t.a;
}
};
node p[110];
ll f[100010], mx;
int main(){
int T, n;
scanf("%d%d", &T, &n);
for(int i = 1; i <= n; i ++) scanf("%lld", &p[i].num);
for(int i = 1; i <= n; i ++) scanf("%lld", &p[i].a);
for(int i = 1; i <= n; i ++) scanf("%lld", &p[i].b);
sort(p+1, p+1+n);
for(int i = 1; i <= n; i ++){
for(int j = T; j >= p[i].b; j --){
f[j] = max(f[j], f[j-p[i].b] + max((ll)0, p[i].num-p[i].a*j));
}
}
for(int i = 0; i <= T; i ++) mx = max(mx, f[i]);
printf("%lld", mx);
return 0;
}

创意吃鱼法

题目来源:【洛谷 1736】

思路:

题目也就是问最长的只有对角线的正方形最大的对角线长度。
f[i][j] 表示以 i j 列结尾的最长的对角线长度, f[i][j] 转移左上的, g[i][j] 转移右上的。
转移的时候要验证新添加的一行或者一列的一部分是否只有 i,j 位置上的一个1,这个可以用二维的前缀和O(NM)预处理,O(1)询问。
每次向前面转移的长度要尽量长,但是有的时候全选上又不满足条件,所以只能选一部分,这里可以二分枚举选多少。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m, mx;
int f[2510][2510], g[2510][2510];
int v[2510][2510], sum[2510][2510];
int calc(int x1, int y1, int x2, int y2){
return sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
scanf("%d", &v[i][j]);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
sum[i][j] = sum[i-1][j] + sum[i][j-1]
- sum[i-1][j-1] + v[i][j];
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
if(!v[i][j]) continue;
if(f[i-1][j-1]){
int l = 1, r = f[i-1][j-1] + 1, ans = 0;
while(l <= r){
int mid = (l+r) >> 1;
if(calc(i,j-mid+1,i,j) == 1
&& calc(i-mid+1,j,i,j) == 1) ans = mid, l = mid + 1;
else r = mid - 1;
}
f[i][j] = ans;
}
f[i][j] = max(f[i][j], 1);
if(g[i-1][j+1]){
int l = 1, r = g[i-1][j+1] + 1, ans = 0;
while(l <= r){
int mid = (l+r) >> 1;
if(calc(i,j,i,j+mid-1) == 1
&& calc(i-mid+1,j,i,j) == 1) ans = mid, l = mid + 1;
else r = mid - 1;
}
g[i][j] = ans;
}
g[i][j] = max(g[i][j], 1);
mx = max(mx, max(f[i][j], g[i][j]));
}
}
printf("%d", mx);
return 0;
}

统计单词个数

题目来源:【洛谷 1026】

思路:

分析题意可以知道,同一个开头的字母只能有一个对应的单词相对应,所以我们可以先进行一次动态规划。设 v[i][j] 表示从第 i 号字符到第 j 号字符的单词个数。
转移:
v[i][j]=v[i+1][j]+1 (存在以 i 开头的单词)
v[i][j]=v[i+1][j] (不存在以 i 开头的单词)
得到 v 数组以后,下一步的就很方便了,设 f[i][j] 表示前 i 个字符,分为 j 段的最大单词数。
转移:
f[i][j]=max(f[k][j1]+v[j+1][i],f[i][j])  jki1
所有的 f[i][1] 都可以提前初始化,转移时不再转移。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <string>
using namespace std;
string s, t, dic[10];
int v[210][210], f[210][210];
int n, m, k;
void init(){
for(int i = 1; i <= n; i ++){
t = s[i];
for(int j = 1; j <= m; j ++)
if(t == dic[j]){v[i][i] = 1;break;}
}
for(int i = 2; i <= n; i ++)
for(int j = 1; i+j-1 <= n; j ++){
bool ok = 0;
string c = "";
for(int p = j; !ok && p <= j+i-1; p ++){
c += s[p];
for(int k = 1; k <= m; k ++)
if(c == dic[k]){ok = 1;break;}
}
if(ok) v[j][j+i-1] = v[j+1][j+i-1] + 1;
else v[j][j+i-1] = v[j+1][j+i-1];
}
return;
}
int main(){
s = " ";
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i ++) cin >> t, s += t;
scanf("%d", &m);
for(int i = 1; i <= m; i ++) cin >> dic[i];
n *= 20, init();
for(int i = 1; i <= n; i ++){
f[i][1] = v[1][i];
for(int l = 2; l <= i && l <= k; l ++){
for(int j = l; j < i; j ++){
f[i][l] = max(f[i][l], f[j][l-1] + v[j+1][i]);
}
}
}
printf("%d", f[n][k]);
return 0;
}

垃圾陷阱

题目来源:【洛谷 1156】

思路:

f[i][j] 表示已经处理了前 i 个垃圾,现在放的高度是 j 的最长存活时间。
递推转移:
f[i+1][j]=max(f[i+1][j],f[i][j]t+p[i+1].b);
f[i+1][min(j+p[i+1].c,H)]=max(f[i+1][min(j+p[i+1].c,H)],f[i][j]t);
显然,以上的方程需要满足条件 (f[i][j]t>=0)
如果没有解,可以重新贪心求出最长的存活时间。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf = 1e9;
struct node{
int a, b, c;
bool operator < (const node &t)const{
return a < t.a;
}
};
node p[110];
int f[110][110], res;
int H, n;
int main(){
scanf("%d%d", &H, &n);
for(int i = 0; i <= n; i ++)
for(int j = 0; j <= H; j ++)
f[i][j] = -inf;
for(int i = 1; i <= n; i ++) scanf("%d%d%d", &p[i].a, &p[i].b, &p[i].c);
f[0][0] = 10;
sort(p+1,p+1+n);
for(int i = 0; i < n; i ++){
for(int j = 0; j <= H; j ++){
int t = p[i+1].a - p[i].a;
if(f[i][j] - t >= 0){
f[i+1][j] = max(f[i+1][j], f[i][j] - t + p[i+1].b);
f[i+1][min(j+p[i+1].c, H)] = max(f[i+1][min(j+p[i+1].c, H)], f[i][j] - t);
}
}
}
for(int i = 1; i <= n; i ++){
if(f[i][H] >= 0){
printf("%d", p[i].a);
return 0;
}
}
int left = 10;
for(int i = 1; i <= n; i ++){
if(p[i].a - p[i-1].a <= left) left = left - (p[i].a - p[i-1].a) + p[i].b;
else{
res = max(p[i-1].a + left, res);
break;
}
res = max(left+p[i].a, res);
}
printf("%d", res);
return 0;
}

过河

题目来源:【洛谷 1052】

思路:

非常裸的背包问题,可以说对一个数取模来缩小范围是不对的做法,可是数据比较水。
直接压缩会被卡在最大值与最小值相等的情况上,所以加上特判,水过,以后有机会一定改正。
正解使用裴蜀定理,解出一个式子,然后就可以求出中间没有用的部分,将其去除。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
const int inf = 1e9;
int v[110], cnt;
int L, S, T, n, p, pp;
int f[2000010];
int main(){
scanf("%d%d%d%d", &L, &S, &T, &n);
for(int i = 1; i <= n; i ++) scanf("%d", &v[i]);
sort(v+1, v+1+n);
if(S == T){
int ans = 0;
for(int i = 1; i <= n; i ++)
if(v[i] % S == 0) ans ++;
printf("%d", ans);
return 0;
}
int left = 0;
for(int i = 1; i <= n; i ++){
v[i] -= left;
int t = (v[i] - v[i-1]) / 1009 * 1009;
left += t;
v[i] -= t;
}
L -= left;
int t = (L - v[n]) / 1009 * 1009;
L -= t;
for(int i = 1; i <= L; i ++) f[i] = inf;
if(v[++p] == 0) f[0] = 1, p ++;
else f[0] = 0;
for(int i = 0; i <= L; i ++){
while(v[p] < i) p ++;
if(v[p] == i) pp = 1;
else pp = 0;
for(int j = S; j <= T; j ++)
f[i+j] = min(f[i+j], f[i] + pp);
}
printf("%d", f[L]);
return 0;
}

加分二叉树

题目来源:【洛谷 1040】

思路:

树的中序遍历可以看做是一个区间dp的模型,每次枚举根节点的位置,根据题目中给出的式子,特判树的根在左端点和右端点的情况。
f[i][j] 表示 i j 这一段区间中,最大的得分是多少, g[i][j] 表示 i j 这一段区间中,选择那个节点为根。
在维护 f 数组的时候,顺便记录 g
转移:
f[j][j+i1]=max(f[j][k1]×f[k+1][j+i1]+f[k][k],f[j][j+i1])

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <string>
using namespace std;
typedef long long ll;
ll n, v[50], f[50][50], g[50][50];
void dfs(ll l, ll r){
if(l == r){cout << l << " ";return;}
cout << g[l][r] << " ";
if(l <= g[l][r]-1) dfs(l,g[l][r]-1);
if(g[l][r]+1 <= r) dfs(g[l][r]+1,r);
return;
}
int main(){
cin >> n;
for(int i = 1; i <= n; i ++) cin >> v[i];
for(int i = 1; i <= n; i ++) f[i][i] = v[i], g[i][i] = i;
for(int i = 2; i <= n; i ++){
for(int j = 1; j+i-1 <= n; j ++){
for(int k = j; k <= j+i-1; k ++){
if(k == j){
if(f[j][j+i-1] < v[j] + f[j+1][j+i-1]){
f[j][j+i-1] = v[j] + f[j+1][j+i-1];
g[j][j+i-1] = k;
}
}
else if(k == j+i-1){
if(f[j][j+i-1] < v[j+i-1] + f[j][j+i-2]){
f[j][j+i-1] = v[j+i-1] + f[j][j+i-2];
g[j][j+i-1] = k;
}
}
else{
if(f[j][j+i-1] < f[j][k-1] * f[k+1][j+i-1] + v[k]){
f[j][j+i-1] = f[j][k-1] * f[k+1][j+i-1] + v[k];
g[j][j+i-1] = k;
}
}
}
}
}
cout << f[1][n] << endl;
dfs(1,n);
return 0;
}

双塔

题目来源:【洛谷 2423】

思路:

f[i][j] 表示前 i 个水晶,高度差为 j 的相对较高的塔的高度。
转移时考虑每个水晶放的位置:

  • 不放这一块水晶: f[i+1][j]=max(f[i+1][j],f[i][j]);
  • 放在高塔上面: f[i+1][j+v[i+1]]=max(f[i+1][j+v[i+1]],f[i][j]+v[i+1]);
  • 放在低塔上面(注意判断新的高度是否超过高塔):
    f[i+1][abs(jv[i+1])]=max(f[i+1][abs(jv[i+1])],(jv[i+1]>0?f[i][j]:f[i][j]+v[i+1]j));

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf = 1e9;
int v[110], sm, ans;
int f[110][4010];
int main(){
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", &v[i]), sm += v[i];
for(int i = 0; i <= n; i ++)
for(int j = 0; j <= sm; j ++)
f[i][j] = -inf;
f[0][0] = 0;
for(int i = 0; i < n; i ++){
for(int j = 0; j <= sm; j ++){
if(f[i][j] >= 0){
f[i+1][j+v[i+1]] = max(f[i+1][j+v[i+1]], f[i][j] + v[i+1]);
f[i+1][abs(j-v[i+1])] = max(f[i+1][abs(j-v[i+1])], (j-v[i+1] > 0 ? f[i][j] : f[i][j]+v[i+1]-j));
f[i+1][j] = max(f[i+1][j], f[i][j]);
}
}
}
for(int i = n; i >= 1; i --)
if(f[i][0] >= 0) ans = max(ans, f[i][0]);
if(ans == 0) printf("Impossible");
else printf("%d", ans);
return 0;
}