Codeforces Round #186 (Div. 2).D
纠结的一道dp。
状态转移方程还是比较好想的,优化比较纠结
3 seconds
256 megabytes
standard input
standard output
Everything is great about Ilya's city, except the roads. The thing is, the only ZooVille road is represented as n holes in a row. We will consider the holes numbered from 1 to n, from left to right.
Ilya is really keep on helping his city. So, he wants to fix at least k holes (perharps he can fix more) on a single ZooVille road.
The city has m building companies, the i-th company needs ci money units to fix a road segment containing holes with numbers of at least li and at most ri. The companies in ZooVille are very greedy, so, if they fix a segment containing some already fixed holes, they do not decrease the price for fixing the segment.
Determine the minimum money Ilya will need to fix at least k holes.
The first line contains three integers n, m, k (1 ≤ n ≤ 300, 1 ≤ m ≤ 105, 1 ≤ k ≤ n). The next m lines contain the companies' description. The i-th line contains three integers li, ri, ci (1 ≤ li ≤ ri ≤ n, 1 ≤ ci ≤ 109).
Print a single integer — the minimum money Ilya needs to fix at least k holes.
If it is impossible to fix at least k holes, print -1.
Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64dspecifier.
10 4 6
7 9 11
6 9 13
7 7 7
3 5 6
17
10 7 1
3 4 15
8 9 8
5 6 8
9 10 6
1 4 2
1 4 10
8 10 13
2
10 1 9
5 10 14
-1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#include <sstream>
#include <iostream>
using namespace std;
#define INF 0x3fffffffffff typedef __int64 LL; struct node
{
int x,y,w;
}g[]; int n,m,k;
LL dp[][];
LL get[][];
LL mx[]; int cmp(node t,node t1)
{
if(t.x!=t1.x)
return t.x<t1.x;
return t.y>t1.y;
} //真的如此碉炸天 int main()
{
//freopen("//home//chen//Desktop//ACM//in.text","r",stdin);
//freopen("//home//chen//Desktop//ACM//out.text","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<;i++)
for(int j=;j<;j++)
dp[i][j]=INF;
memset(get,,sizeof(get));
memset(g,,sizeof(g));
for(int i=;i<m;i++)
{
scanf("%d%d%d",&g[i].x,&g[i].y,&g[i].w);
g[i].y=g[i].y-g[i].x;
}
sort(g,g+m,cmp);
int i=,j=;
LL mi = INF;
int tmp;
while( i <= n )
{
mi=INF;
tmp=n;
while(g[j].x == i)
{
for(int i1=tmp;i1>=g[j].y;i1--)
get[i][i1]=mi;
tmp=g[j].y;
mi=min(mi,(__int64)g[j].w);
j++;
}
for(int i1=tmp;i1>=;i1--)
get[i][i1]=mi;
i++;
}
for(i=;i<=k;i++)
mx[i]=INF; // 0个的时候,不需要w
// 很好的dp压缩!
for(i=;i<=n;i++)
{
if(get[i][]!=INF)
{
for(j=;j <k;j++)
{
for(int i1=;i1+j<k;i1++)
dp[i+j][i1+j+]=min(dp[i+j][i1+j+],mx[i1]+get[i][j]); //纠结的状态转移方程!
}
}
for(j=;j<=k;j++)
{
mx[j]=min(mx[j],dp[i][j]); // 每一个都是独立的!
dp[i][j]=mx[j];
}
}
if(mx[k]==INF)
printf("-1");
else
printf("%I64d",mx[k]);
return ;
}
最新文章
- JSTREE 实现AJAX重载入时刷新所有节点树
- C#交错数组的用法
- 《OOC》笔记(2)——C语言实现trycatchfinally
- CentOS7安装mysql5.6.23
- 47. Largest Rectangle in Histogram &;&; Maximal Rectangle
- CmdBuild
- SQL Server-游标使用
- 爬虫技术 -- 基础学习(四)HtmlParser基本认识
- 为什么数值类型byte取值范围是(-128~127)?
- 随机分类器的ROC和Precision-recall曲线
- LeetCode Reverse Linked List (反置链表)
- Luogu P1073 最优贸易
- .Net core2.0+Mysql5.7部署到CentOS7.5完整实践经验
- WPF: Hide grid row
- 软件工程——HelloWorld
- String、StringBuffer 的使用 ,两个面试问题
- bbs项目中的零碎点记录
- js-ES6学习笔记-Promise对象
- 【MVC】View与Control之间数据传递
- chromedriver 代理设置(账号密码)