1 条题解
-
0
使用 long long 和正确的无穷大,避免 int 初始化常量溢出。
#include <bits/stdc++.h> using namespace std; int main(){int m,n;cin>>m>>n;vector<long long>x(m+1);for(int i=2;i<=m;i++){cin>>x[i];x[i]+=x[i-1];}vector<vector<long long>>c(m+1,vector<long long>(m+1));for(int l=1;l<=m;l++)for(int r=l+1;r<=m;r++)c[l][r]=c[l][r-1]+x[r]-x[(l+r)/2];const long long INF=LLONG_MAX/4;vector<long long>a(m+1,INF);a[0]=0;for(int schools=1;schools<=n;schools++){vector<long long>b(m+1,INF);for(int r=schools;r<=m;r++)for(int l=schools-1;l<r;l++)b[r]=min(b[r],a[l]+c[l+1][r]);a=b;}cout<<a[m]<<"\n";}
- 1
信息
- ID
- 3873
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 3
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者