洛谷P2426删数

考不好不改名

题目链接（https://www.luogu.com.cn/problem/P2426），区间类动态规划

我得到的状态转移方程式：
f[j] 表示第 i 个数 到第 j 个数删数后的最大操作价值

1. f[i][j] = max{
   
2.     f[i][j - 1] + a[j],
   
3.     f[i + 1][j] + a[i],
   
4.     f[i + k][j] + abs(a[i] - a[i + k - 1]) * k | 1 < k < j - i + 1,
   
5.     f[i][j - k] + abs(a[j] - a[j - k + 1]) * k | 1 < k < j - i + 1
   
6. }

复制代码

我写的代码：

1. #include <iostream>
   
2. 
   
3. int a[105];
   
4. 
   
5. int mem[105][105];
   
6. 
   
7. int f(int, int);
   
8. int max(int, int);
   
9. int abs(int);
   
10. 
    
11. int main(){
    
12.     int n;
    
13. 
    
14.     std::cin >> n;
    
15. 
    
16.     for(int i = 0;i < n;i++){
    
17.         std::cin >> a[i];
    
18.     }
    
19. 
    
20.     std::cout << f(0, n - 1);
    
21. 
    
22.     return 0;
    
23. }
    
24. 
    
25. int f(int i, int j){
    
26.     if(i == j){
    
27.         return a[i];
    
28.     }
    
29.     if(mem[i][j]) return mem[i][j];
    
30. 
    
31.     int ans = max(f(i, j - 1) + a[j], f(i + 1, j) + a[i]);
    
32. 
    
33.     for(int k = 2;k <= j - i;k++){
    
34.         ans = max(ans, f(i + k, j) + abs(a[i] - a[i + k - 1]) * k);
    
35.         ans = max(ans, f(i, j - k) + abs(a[j] - a[j - k + 1]) * k);
    
36.     }
    
37. 
    
38.     return mem[i][j] = ans;
    
39. }
    
40. 
    
41. int max(int a, int b) {return a > b ? a : b;}
    
42. 
    
43. int abs(int n) {return n < 0 ? -n : n;}

复制代码

我卡住的测试数据：

1. 79
   
2. 14 422 61 439 154 228 296 153 346 67 329 276 331 565 79 142 131 137 49 58 78 37 287 288 326 428 322 258 308 233 180 204 552 208 85 138 352 273 343 292 9 214 200 272 413 77 364 28 323 353 448 217 94 106 423 502 126 194 518 46 183 151 127 270 357 489 68 129 412 498 473 84 117 427 160 563 10 91 559

复制代码

应当输出的答案：

1. 43371

复制代码

考不好不改名

捞

考不好不改名

已解决：没有考虑全部数一次一起删去的情况