洛谷题号：P2734
挺难的一道区间型动规，并不会做，看的题解，需要继续学习：
参考题解：https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P2734 作者: redbag 管理员 更新时间: 2016-08-12 11:04
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | #include<iostream> #include<cstdio> #include<string> #include<algorithm> #include<queue> #include<list> #include<cstring> #include<cassert> using namespace std; int n; int num[105],sum[105]; int f[105][105]; int main(){ ios::sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; i++){ cin >> num[i]; sum[i] = sum[i - 1] + num[i]; f[i][i] = num[i]; } for (int i = n - 1; i >= 1; i--){ for (int j = i + 1; j <= n; j++){ f[i][j] = max(sum[j] - sum[i - 1] - f[i + 1][j], sum[j] - sum[i - 1] - f[i][j - 1]); } } cout << f[1][n] << " " << sum[n] - f[1][n] << endl; } |