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