| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:不知道是我题读错了还是测试数据有问题In Reply To:不知道是我题读错了还是测试数据有问题 Posted by:1966412011 at 2019-10-06 23:13:57 > 按照提上的意思,如果有第0秒,第0秒也应该有有牛,我有一份代码,测试数据
> 3 0 4
> 0 0 1
> 1 2 3
> 3 4 1
> 我的代码输出4,这个代码依然可以通过
#include <cstdio>
#include <iomanip>
#include <string>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
//#include <unordered_map>
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define l(x) x<<1
#define r(x) x<<1|1
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node {
int s;
int t;
int val;
};
bool cmp(const node& a, const node& b) {
return a.t < b.t;
}
int n, m, e;
int dp[90000];
node demo[11000];
const int MAX_N = 1 << 17;
int len, dat[2 * MAX_N - 1];
void init(int n_) {
len = 1;
while (len < n_)
len *= 2;
for (int i = 0; i < len * 2 - 1; i++)
dat[i] = INF;
}
void update(int k, int a) {
k += len - 1;
dat[k] = a;
while (k > 0) {
k = (k - 1) / 2;
dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
}
}
int query(int a,int b,int k,int l,int r){
if (r <= a || b <= l)
return INF;
if (a <= l && r <= b) return dat[k];
else {
int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
return min(vl, vr);
}
}
int query(int a, int b) {
return query(a, b, 0, 0, len);
}
int get(int k) {
return dat[k + len - 1];
}
int main(void) {
scanf("%d%d%d", &n, &m, &e);
for (int i = 0; i < n; i++) {
scanf("%d%d%d", &demo[i].s, &demo[i].t,&demo[i].val);
}
init(e);
update(m, 0);
sort(demo, demo + n,cmp);
ms(dp, INF);
dp[0] = 0;
for (int i = 0; i < n; i++) {
int v = min(dp[demo[i].t], query(demo[i].s - 1, demo[i].t+1)+ demo[i].val);
dp[demo[i].t] = v;
update(demo[i].t, v);
}
if(dp[e]!=INF)
printf("%d\n", dp[e]);
else
printf("-1\n");
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator