- 题目大意：给定一个长度为
的序列，至多将序列分成
段，每段序列都有权值，权值为序列内两个数两两相乘之和。求序列权值和最小为多少？ - 数据规模： m
m- 分析：令
表示区间
中两两乘积之和,
表示前
个数分成
段的最小值。
可以转换为
其中
表示前j个数的前缀和。令
则有：
此为直线方程，
为定值，要求
(
为定值)最小，即为直线的截距最小。平面上有若干点
,这些点是由各个决策点产生的。而将直线从下往上平移，它接触到的第一个点即为最佳决策点。因为斜率是上升的，所以，下一阶段的直线方程斜率更高，于是最佳决策点一定形成了下凸包序列。
还可以用滚动数组…具体见代码:
#include
using namespace std;
const int MAXN = 1005;
#define LL long long
int n, m, s, t, dq[MAXN];
LL sum[MAXN], w[MAXN], f[2][MAXN];
inline LL Getup(int now, int i, int j) { return (f[now][i] + sum[i]*sum[i] - w[i]) - (f[now][j] + sum[j]*sum[j] - w[j]); }//Yi-Yj
inline LL Getdown(int now, int i, int j) { return sum[i] - sum[j]; }//Xi-Xj
int main ()
{
int x;
while(scanf("%d%d", &n, &m), n || m)
{
for(int i = 1; i 1 && Getup(now^1, dq[s+1], dq[s]) 1 && Getup(now^1, j, dq[t-1]) * Getdown(now^1, dq[t-1], dq[t-2]) 服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net
