B：打比赛
题目大意： 一个由三个人组成的ACM队去参加world final 题目非常多 在比赛开始的一瞬间 每个人都对每道题的难度做出了一个预判 分为五个级别 1～5 他们想采取这样的A题策略： 1. 将所有题分成三段连续的区间 2. 每个区间非空 3. 每人认领一段区间 4. 难度的总值为 每个人的难度估值在认领的区间的和 的和 5. 使得难度总值最小 然后求出这个最小的难度总值
别走来就想DP
code
// #include<bits/stdc++.h> using namespace std; #define ll long long ll n; #define maxnn 300010 ll sum[maxnn][4]; ll ans=1e18; void work(ll a,ll b,ll c) { ll num1=1e18,num2=1e18; ll las=0; int j=1; for(int i=2;i<n;i++) { ans=min(ans,sum[n][c]+sum[j][a]-sum[j][b]+sum[i][b]-sum[i][c]);//双变量O(n)比较最优值 if(num2>sum[i][a]-sum[i][b]) { num2=min(num2,sum[i][a]-sum[i][b]); j=i; } } } int main() { scanf("%lld",&n); ll x,y,z; for(int j=1;j<=3;j++) for(int i=1;i<=n;i++) { scanf("%lld",&x); sum[i][j]=sum[i-1][j]+x; } work(1,2,3); work(1,3,2); work(2,1,3); work(2,3,1); work(3,1,2); work(3,2,1); printf("%lld",ans); }
原文：https://www.cnblogs.com/OIEREDSION/p/11173882.html