NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #197734 | #2717. 8.2t2 | wosile | 100 | 107ms | 1516kb | C++11 | 621b | 2023-11-14 09:07:06 | 2023-11-14 12:02:09 |
answer
#include<bits/stdc++.h>
using namespace std;
int f[205][205],mx[205][205];
int a[205],T,n;
int pre[205];
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
mx[i][i]=a[i];
for(int j=i+1;j<=n;j++)mx[i][j]=max(mx[i][j-1],a[j]);
}
for(int i=1;i<=n;i++)for(int j=0;j<=n;j++){
f[i][j]=f[i-1][j]+a[i];
if(j>0)f[i][j]=max(f[i][j],f[i][j-1]);
for(int k=0;k<i;k++)if(j>=(i-k)/2)f[i][j]=max(f[i][j],f[k][j-(i-k)/2]+mx[k+1][i]*(i-k));
}
for(int i=1;i<=n;i++)printf("%d ",f[n][i]);
putchar(10);
}
return 0;
}
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1200kb
input:
10 5 11 4 11 12 15 5 7 2 14 19 6 5 4 6 8 7 2 5 14 10 3 15 12 5 1 6 3 2 6 5 5 15 12 20 13 5 20 18 9 5...
output:
62 75 75 75 75 70 95 95 95 95 34 40 40 40 40 71 75 75 75 75 26 30 30 30 30 80 100 100 100 100 ...
result:
ok 50 numbers
Test #2:
score: 10
Accepted
time: 0ms
memory: 1204kb
input:
10 5 9 4 11 15 4 5 4 19 1 12 15 5 2 20 14 4 10 5 12 15 11 19 7 5 14 8 17 15 2 5 7 19 13 1 17 5 11 12...
output:
58 75 75 75 75 84 95 95 95 95 74 100 100 100 100 84 95 95 95 95 73 85 85 85 85 81 95 95 95 95 ...
result:
ok 50 numbers
Test #3:
score: 10
Accepted
time: 0ms
memory: 1200kb
input:
10 5 8 2 19 16 13 5 4 8 5 17 5 5 11 5 13 17 20 5 3 9 19 6 15 5 13 7 20 6 5 5 1 18 11 10 5 5 2 2 6 12...
output:
86 95 95 95 95 63 85 85 85 85 82 100 100 100 100 78 95 95 95 95 80 100 100 100 100 69 90 90 90 ...
result:
ok 50 numbers
Test #4:
score: 10
Accepted
time: 1ms
memory: 1220kb
input:
10 15 11 16 14 18 17 1 20 8 18 1 3 8 16 18 8 15 4 10 14 10 7 14 5 1 20 1 10 12 19 12 14 15 7 4 17 1 ...
output:
209 240 258 270 279 287 300 300 300 300 300 300 300 300 300 191 216 235 253 277 291 300 300 300 300...
result:
ok 150 numbers
Test #5:
score: 10
Accepted
time: 0ms
memory: 1216kb
input:
10 15 9 17 4 3 17 3 12 10 7 11 2 15 5 1 9 15 10 20 1 6 13 16 3 17 11 12 1 1 6 15 20 15 6 16 8 4 16 2...
output:
153 177 198 217 233 247 255 255 255 255 255 255 255 255 255 185 209 242 262 280 297 300 300 300 300...
result:
ok 150 numbers
Test #6:
score: 10
Accepted
time: 0ms
memory: 1216kb
input:
10 15 11 15 20 2 20 18 7 19 20 17 3 18 19 18 11 15 1 19 16 19 18 2 1 19 4 5 14 8 18 2 18 15 3 12 18 ...
output:
241 261 276 286 295 300 300 300 300 300 300 300 300 300 300 199 228 254 275 283 285 285 285 285 285...
result:
ok 150 numbers
Test #7:
score: 10
Accepted
time: 2ms
memory: 1272kb
input:
10 50 4 14 15 20 12 15 1 19 16 3 1 19 2 17 6 20 20 1 18 3 3 9 7 10 14 4 6 8 12 5 17 17 17 3 10 16 18...
output:
602 634 664 689 713 736 758 782 804 825 845 864 882 901 919 933 949 961 973 984 990 995 1000 1000 10...
result:
ok 500 numbers
Test #8:
score: 10
Accepted
time: 2ms
memory: 1276kb
input:
10 50 18 15 12 10 12 20 18 1 13 9 13 14 2 7 8 11 4 12 18 5 4 7 7 2 5 11 10 4 3 18 7 19 16 18 14 19 1...
output:
533 560 586 614 641 664 692 715 738 760 780 802 824 843 866 889 912 930 947 961 970 977 987 998 1000...
result:
ok 500 numbers
Test #9:
score: 10
Accepted
time: 2ms
memory: 1276kb
input:
10 50 4 16 4 16 1 3 18 7 12 4 6 13 6 7 3 14 9 4 12 12 2 8 12 13 8 1 8 9 13 5 18 17 19 20 16 16 13 5 ...
output:
501 531 559 587 617 643 667 686 710 731 753 774 793 817 835 854 874 900 924 945 963 974 989 1000 100...
result:
ok 500 numbers
Test #10:
score: 10
Accepted
time: 100ms
memory: 1516kb
input:
10 200 37 114 93 127 119 140 8 63 134 2 137 36 119 112 73 142 60 177 100 70 153 105 53 138 46 180 13...
output:
19916 20240 20544 20842 21138 21429 21717 22001 22285 22568 22851 23125 23401 23675 23943 24209 2447...
result:
ok 2000 numbers
