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. Input
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). Output
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 %I64d specifier. Sample test(s) Input
10 4 6 7 9 11 6 9 13 7 7 7 3 5 6
Output
17
Input
10 7 1 3 4 15 8 9 8 5 6 8 9 10 6 1 4 2 1 4 10 8 10 13
Output
2
Input
10 1 9 5 10 14
Output
-1
dp[i][j] 表示前i个点，，埋了j个的最小代价 C[i][j]表示从i到j雇佣一家公司埋好花的最少的钱
/*************************************************************************> File Name: CF-186-D.cpp> Author: ALex> Mail: zchao1995@gmail.com> Created Time: 2015年04月02日 星期四 16时39分36秒 ************************************************************************/;const double pi = acos(-1.0);const double eps = 1e-15;LL;const LL inf = (1LL << 60);typedef pair <int, int> PLL;const int N = 330;LL C[N][N];LL dp[N][N];int main(){int n, m, k;while (~scanf(“%d%d%d”, &n, &m, &k)){int l, r;LL c;for (int i = 0; i <= n + 1; ++i){for (int j = 0; j <= n + 1; ++j){dp[i][j] = inf;C[i][j] = inf;}}for (int i = 0; i <= n; ++i){dp[i][0] = 0;}for (int i = 1; i <= m; ++i){scanf(“%d%d%lld”, &l, &r, &c);C[l][r] = min(C[l][r], c);}for (int i = 1; i <= n; ++i){for (int j = n; j >= i; –j){C[i][j] = min(C[i][j], C[i – 1][j]);C[i][j] = min(C[i][j], C[i][j + 1]);}}for (int i = 1; i <= n; ++i){for (int j = 1; j <= i; ++j){dp[i][j] = dp[i – 1][j];for (int p = 0; p < i; ++p){if (C[p + 1][i] == inf){continue;}dp[i][j] = min(dp[i][j], dp[p][j – i + p] + C[p + 1][i]);}}}LL ans = inf;for (int i = 1; i <= n; ++i){for (int j = k; j <= i; ++j){ans = min(ans, dp[i][j]);}}if (ans >= inf){ans = -1;}printf(“%lld\n”, ans);}return 0;}
我爱你….为了你的幸福，我愿意放弃一切—包括你。
