luoguP4360 [CEOI2004]锯木厂选址

题目链接

luoguP4360 [CEOI2004]锯木厂选址

题解

dis:后缀和
sum:前缀和
补集转化，减去少走的，得到转移方程
dp[i] = min(tot - sumj * disj - (sumi - sumj) * disi
不需要斜率优化吧？反正也是个SB式子

代码

#include<bits/stdc++.h> 
using namespace std; 
inline int read() { 
    int x = 0,f = 1; 
    char c = getchar(); 
    while(c < '0' ||c > '9')c = getchar(); 
    while(c <= '9' && c >= '0')x = x* 10 + c -'0',c = getchar(); 
    return x *f ; 
} 
const int maxn  = 200007; 
int dp[maxn],dis[maxn],sum[maxn]; 
int tot = 0;  
int main() { 
    int n = read(); 
    for(int a,b,i = 1;i <= n;++ i) { 
        a = read(),b = read(); 
        sum[i] = sum[i - 1] + a; dis[i] += b; 
        tot += sum[i] * b; 
    } 
    for(int i = n;i >= 1;-- i) dis[i] = dis[i] + dis[i + 1]; 
    //printf("%d
",tot); 
    memset(dp,0x3f,sizeof dp); 
    int ans = 0x3f3f3f3f; 
    for(int i = 1;i <= n;++ i) {
        for(int j = 1;j < i;++ j)  {
            dp[i] = min(tot - sum[j] * dis[j] - (sum[i] - sum[j]) * dis[i],dp[i]); 
        } 
        ans = min(ans,dp[i]); 
    } 
    printf("%d
",ans); 
    return 0; 
}