SEQPART (IOI'14)
Xem PDF
Điểm:
1900 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho dãy \(L\) gồm các số \(C[1..L]\), cần chia dãy này thành \(G\) đoạn liên tiếp. Với phần tử thứ \(i\), ta định nghĩa chi phí của nó là tích của \(C_i\) và số lượng các số nằm cùng đoạn liên tiếp với \(C_i\). Chi phí của dãy số ứng với một cách phân hoạch là tổng các chi phí của các phần tử của G đoạn đã chia.
Yêu cầu: Hãy xác định cách phân hoạch dãy số để chi phí là nhỏ nhất.
Input
- Dòng đầu tiên chứa 2 số \(L\) và \(G\).
- \(L\) dòng tiếp theo, chứa giá trị của dãy \(C_1, C_2, …, C_n\).
Output
- In một dòng duy nhất là chi phí nhỏ nhất.
Scoring
- \(1 ≤ L ≤ 8000\).
- \(1 ≤ G ≤ 800\).
- \(1 ≤ C_i ≤ 10^9\).
Example
Test 1
Input
6 3
11
11
11
24
26
100
Output
299Note
- Cách tối ưu là \(C[]=(11,11,11), (24,26), (100)\) Chi phí \(11∗3 + 11∗3 + 11∗3 + 24∗2 + 26∗2 + 100∗1=299\).
Bình luận
include <bits/stdc++.h>
using namespace std;
int64_t dp[801][8001];
int vt[801][8001];
int64_t s[8001];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n,k;
cin>>n>>k;
for(int i=1; i<=n; i++)
{
cin>>s[i];
s[i]+=s[i-1];
}
for(int i=0; i<=n; i++)
{
dp[0][i]=1ll(s[i]-s[0])(i);
//vt[0][i]=0;
}
int r,l;
for(int j=1; j<k; j++) { for(int i=n; i>=1; i--)
{
dp[j][i]=dp[j-1][i-1]+1ll(s[i]-s[i-1]);
vt[j][i]=i-1;
if(i==n)
{
r=n-1;
}
else
{
r=min(i-1,vt[j][i+1]);
}
l=vt[j-1][i];
for(int p=r; p>=l; p--)
{
if(dp[j-1][p]+1ll(s[i]-s[p])(i-p)<dp[j][i])
{
dp[j][i]=dp[j-1][p]+1ll1ll(s[i]-s[p])(i-p);
vt[j][i]=p;
}
}
}
}
cout<<dp[k-1][n];
}