Acwing282.石子合并（区间DP）

区间DP问题&＃xff0c;设f[i][j]表示合并 i ~ j 堆石子所需要的最小代价。

#include using namespace std;const int N &＃61; 310;int n , a[N] , s[N] , f[N][N];int main()
{cin >> n;for(int i &＃61; 1; i <&＃61; n; i &＃43;&＃43;) cin >> a[i];// 处理前缀和for(int i &＃61; 1; i <&＃61; n; i &＃43;&＃43;) s[i] &＃61; s[i-1] &＃43; a[i];for(int len &＃61; 2; len <&＃61; n; len &＃43;&＃43;) // 枚举长度{for(int i &＃61; 1; i &＃43; len - 1 <&＃61; n; i &＃43;&＃43;) // 枚举起点{int j &＃61; i &＃43; len - 1;f[i][j] &＃61; 0x3f3f3f3f; // 初始化为正无穷for(int k &＃61; i; k <&＃61; j - 1; k &＃43;&＃43;){f[i][j] &＃61; min(f[i][j] , f[i][k] &＃43; f[k&＃43;1][j] &＃43; s[j] - s[i-1]);}}}cout << f[1][n] << endl;return 0;
}