题目
Pearls的替代必须是连续的，否则会有更优策略，这不难证明。定义状态dp[i]表示在已知第i类珍珠时,所需支付的最低价格
则状态方程为：
dp[i]=(a[i]+10)*p[i]+dp[i-1] //当第i种珍珠出现时，未优化价格的情况
dp[i]=min((sum[i]-sum[j]+10)*p[i]+dp[j]) //枚举j，价格优化
dp[i]=min(dp[j]-sum[j] *p[i]) + sum[i]*p[i]+10*p[i]
dp[j] – dp[k] < p[i]*(sum[j] – sum[k])
斜率优化。
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
#define N 110
#define cls(a) memset(a,0,sizeof(a))
struct P{int x, y;
};P q[1000];
int dp[N], a[N], sum[N], p[N], n, l, r;P operator - ( P a, P b ){P p;p.x = a.x - b.x;p.y = a.y - b.y;return p;
}int operator * ( P a, P b ){return a.x*b.y - a.y*b.x;
}void init(){//cls(dp), cls(a), cls(sum), cls(p), cls(q);scanf( "%d", &n);for ( int i = 1; i <= n; i++) scanf( "%d%d", &a[i], &p[i]);for ( int i = 1; i <= n; i++) sum[i] = sum[i-1] + a[i];l=1, r=2;dp[0]=0, dp[1] = sum[1]*p[1] + ( sum[1]+10 )*p[1];q[1].x=sum[1], q[1].y=dp[1];
}void insert(int x, int y ){P p;p.x = x, p.y = y;for(;l<r && (p-q[r-1])*(q[r]-q[r-1])>=0;r--);q[++r] = p;
}void Dp(){for ( int i = 1; i <= n; i++){int k = p[i];for (;l<r && q[l].y-k*q[l].x > q[l+1].y-k*q[l+1].x;l++);dp[i] = q[l].y - k*q[l].x + (sum[i]+10)*p[i];insert(sum[i], dp[i]);}printf( "%d\n", dp[n]);
}int main(){int T;scanf( "%d", &T);while ( T-- ){init();Dp();}return 0;
}
/*
2
2
100 1
100 2
3
1 10
1 11
100 12*/