(建议您从上方链接进入我的个人网站查看此 Blog,在 Luogu 中图片会被墙掉,部分 Markdown 也会失效)
做这道题的原因是在写 POI 的一道人类智慧题的时候有点想不明白,然后看题解里有人说中间有一步和这道题的思路差不多,于是决定先把这道题做一下。
给你 Impossible
。
Input_1
xxxxxxxxxx
215
21 3 4 5 2
Output_1
xxxxxxxxxx
117
第一次听说还有这种状态设计
令
我们考虑转移,显然可以分成以下几种情况:
关于第四个方程可以看下面这个图,不难发现有
所以转移就是上面四个式子求最大值即可。
复杂度
xxxxxxxxxx
701
2
3
4
5
6
7
8
9
10
11/******************************
12abbr
13
14******************************/
15
16using namespace std;
17using namespace __gnu_pbds;
18
19mt19937 rnd(random_device{}());
20int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
21bool rnddd(int x){return rndd(1, 100) <= x;}
22
23typedef unsigned int uint;
24typedef unsigned long long unll;
25typedef long long ll;
26typedef long double ld;
27
28template<typename T = int>
29inline T read(void);
30
31
32int N;
33int h[110];
34int dp[110][2100];
35
36int main(){
37 dp[0][0] = 0;
38 for(int i = 1; i <= 2010; ++i)dp[0][i] = MINF;
39 N = read();
40 int sum(0);
41 for(int i = 1; i <= N; ++i)h[i] = read(), sum += h[i];
42 for(int i = 1; i <= N; ++i){
43 for(int j = 0; j <= sum; ++j){
44 dp[i][j] = dp[i - 1][j];
45 if(j >= h[i])dp[i][j] = max(dp[i][j], dp[i - 1][j - h[i]] + h[i]);
46 else dp[i][j] = max(dp[i][j], dp[i - 1][h[i] - j] + j);
47 if(j + h[i] <= sum)dp[i][j] = max(dp[i][j], dp[i - 1][j + h[i]]);
48 }
49 }
50 if(dp[N][0] > 0)printf("%d\n", dp[N][0]);
51 else printf("Impossible\n");
52 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
53 return 0;
54}
55
56template<typename T>
57inline T read(void){
58 T ret(0);
59 short flag(1);
60 char c = getchar();
61 while(c != '-' && !isdigit(c))c = getchar();
62 if(c == '-')flag = -1, c = getchar();
63 while(isdigit(c)){
64 ret *= 10;
65 ret += int(c - '0');
66 c = getchar();
67 }
68 ret *= flag;
69 return ret;
70}
xxxxxxxxxx
681
2
3
4
5
6
7
8
9
10
11/******************************
12abbr
13
14******************************/
15
16using namespace std;
17using namespace __gnu_pbds;
18
19// mt19937 rnd(random_device{}());
20// int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
21// bool rnddd(int x){return rndd(1, 100) <= x;}
22
23typedef unsigned int uint;
24typedef unsigned long long unll;
25typedef long long ll;
26typedef long double ld;
27
28template<typename T>
29inline T read(void){
30 T ret(0);
31 short flag(1);
32 char c = getchar();
33 while(c != '-' && !isdigit(c))c = getchar();
34 if(c == '-')flag = -1, c = getchar();
35 while(isdigit(c)){
36 ret *= 10;
37 ret += int(c - '0');
38 c = getchar();
39 }
40 ret *= flag;
41 return ret;
42}
43
44
45
46int N;
47int h[110];
48int dp[110][2100];
49
50int main(){
51 dp[0][0] = 0;
52 for(int i = 1; i <= 2010; ++i)dp[0][i] = MINF;
53 N = read();
54 int sum(0);
55 for(int i = 1; i <= N; ++i)h[i] = read(), sum += h[i];
56 for(int i = 1; i <= N; ++i){
57 for(int j = 0; j <= sum; ++j){
58 dp[i][j] = dp[i - 1][j];
59 if(j >= h[i])dp[i][j] = max(dp[i][j], dp[i - 1][j - h[i]] + h[i]);
60 else dp[i][j] = max(dp[i][j], dp[i - 1][h[i] - j] + j);
61 if(j + h[i] <= sum)dp[i][j] = max(dp[i][j], dp[i - 1][j + h[i]]);
62 }
63 }
64 if(dp[N][0] > 0)printf("%d\n", dp[N][0]);
65 else printf("Impossible\n");
66 // fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
67 return 0;
68}
update-2022_09_27 初稿