本文共 7694 字，大约阅读时间需要 25 分钟。
线段树+SPFA最短路可以过。或者DP也能过。
1 /* 2155 */ 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 using namespace std; 23 //#pragma comment(linker,"/STACK:102400000,1024000") 24 25 #define sti set 26 #define stpii set > 27 #define mpii map 28 #define vi vector 29 #define pii pair 30 #define vpii vector > 31 #define rep(i, a, n) for (int i=a;i =a;--i) 33 #define clr clear 34 #define pb push_back 35 #define mp make_pair 36 #define fir first 37 #define sec second 38 #define all(x) (x).begin(),(x).end() 39 #define SZ(x) ((int)(x).size()) 40 #define lson l, mid, rt<<1 41 #define rson mid+1, r, rt<<1|1 42 43 typedef struct { 44 int v, w, nxt; 45 } edge_t; 46 47 typedef struct node_t { 48 int xl, xr, y; 49 50 node_t() {} 51 node_t(int xl, int xr, int y): 52 xl(xl), xr(xr), y(y) {} 53 54 friend bool operator <(const node_t& a, const node_t& b) { 55 return a.y < b.y; 56 } 57 58 } node_t; 59 60 const int maxv = 1025; 61 const int maxe = maxv * 1000; 62 const int INF = 0x3f3f3f3f; 63 int n, x, y, mx, T; 64 edge_t E[maxe]; 65 int head[maxv<<1]; 66 bool visit[maxv<<1]; 67 int dis[maxv<<1]; 68 node_t nd[maxv]; 69 int l = 0, m; 70 int start, End; 71 int ID[maxv<<2]; 72 int L, R, id; 73 74 void init() { 75 l = 0; 76 m = 1; 77 memset(head, -1, sizeof(head)); 78 } 79 80 void addEdge(int u, int v, int w) { 81 E[l].v = v; 82 E[l].w = w; 83 E[l].nxt = head[u]; 84 head[u] = l++; 85 } 86 87 void Build(int l, int r, int rt) { 88 ID[rt] = 0; 89 if (l == r) 90 return ; 91 92 int mid = (l + r) >> 1; 93 Build(lson); 94 Build(rson); 95 } 96 97 inline void PushDown(int rt) { 98 if (ID[rt]) { 99 ID[rt<<1] = ID[rt<<1|1] = ID[rt];100 ID[rt] = 0;101 }102 }103 104 void Update(int l, int r, int rt) {105 if (L<=l && R>=r) {106 ID[rt] = id;107 return ;108 }109 110 PushDown(rt);111 int mid = (l + r) >> 1;112 113 if (R <= mid) {114 Update(lson);115 } else if (L > mid) {116 Update(rson);117 } else {118 Update(lson);119 Update(rson);120 }121 }122 123 int Query(int k, int l, int r, int rt) {124 if (l == r)125 return ID[rt];126 127 PushDown(rt);128 int mid = (l + r) >> 1;129 130 if (k <= mid)131 return Query(k, lson);132 else133 return Query(k, rson);134 }135 136 int spfa() {137 queue Q;138 int u, v, k;139 140 memset(visit, false, sizeof(visit));141 memset(dis, INF, sizeof(dis));142 dis[start] = 0;143 visit[start] = true;144 Q.push(start);145 146 while (!Q.empty()) {147 u = Q.front();148 Q.pop();149 visit[u] = false;150 for (k=head[u]; k!=-1; k=E[k].nxt) {151 v = E[k].v;152 if (dis[u]+E[k].w < dis[v]) {153 dis[v] = dis[u] + E[k].w;154 if (!visit[v]) {155 visit[v] = true;156 Q.push(v);157 }158 }159 }160 }161 162 return dis[End];163 }164 165 int main() {166 ios::sync_with_stdio(false);167 #ifndef ONLINE_JUDGE168 freopen("data.in", "r", stdin);169 freopen("data.out", "w", stdout);170 #endif171 172 int t;173 int lid, rid;174 int tmp, w;175 176 scanf("%d", &t);177 rep(tt, 1, t+1) {178 scanf("%d %d %d %d %d", &n, &x, &y, &mx, &T);179 ++x;180 init();181 rep(i, 0, n) {182 scanf("%d %d %d", &nd[m].xl, &nd[m].xr, &nd[m].y);183 ++nd[m].xl;184 ++nd[m].xr;185 if (nd[m].y < y)186 ++m;187 }188 189 nd[m].xl = x;190 nd[m].xr = x;191 nd[m].y = y;192 ++m;193 nd[m].xl = 1;194 nd[m].xr = 1002;195 nd[m].y = 0;196 sort(nd+1, nd+1+m);197 End = 1;198 start = m;199 memset(ID, 0, sizeof(ID));200 201 L = nd[1].xl;202 R = nd[1].xr;203 id = 1;204 Update(1, 1005, 1);205 rep(i, 2, m+1) {206 207 // handle left208 L = nd[i].xl;209 lid = Query(L, 1, 1005, 1);210 tmp = nd[i].y - nd[lid].y;211 if (tmp <= mx) {212 if (lid == End) {213 w = tmp;214 addEdge(i, lid, w);215 } else {216 // to left of lid217 w = tmp + nd[i].xl - nd[lid].xl;218 addEdge(i, lid, w);219 220 // to right of lid221 w = tmp + nd[lid].xr - nd[i].xl;222 addEdge(i, lid+m, w);223 }224 }225 226 // handle right227 if (i != m) {228 R = nd[i].xr;229 rid = Query(R, 1, 1005, 1);230 tmp = nd[i].y - nd[rid].y;231 if (tmp <= mx) {232 if (rid == End) {233 w = tmp;234 addEdge(i+m, rid, w);235 } else {236 // to left of rid237 w = tmp + nd[i].xr - nd[rid].xl;238 addEdge(i+m, rid, w);239 240 // to right of rid241 w = tmp + nd[rid].xr - nd[i].xr;242 addEdge(i+m, rid+m, w);243 }244 }245 }246 247 L = nd[i].xl;248 R = nd[i].xr;249 id = i;250 251 Update(1, 1005, 1);252 }253 254 tmp = spfa();255 if (tmp==INF || tmp>T)256 puts("YES");257 else258 puts("NO");259 }260 261 #ifndef ONLINE_JUDGE262 printf("time = %d.\n", (int)clock());263 #endif264 265 return 0;266 }
2. DP, 二维DP，没什么好说的。
1 /* 2155 */ 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 using namespace std; 23 //#pragma comment(linker,"/STACK:102400000,1024000") 24 25 #define sti set 26 #define stpii set > 27 #define mpii map 28 #define vi vector 29 #define pii pair 30 #define vpii vector > 31 #define rep(i, a, n) for (int i=a;i =a;--i) 33 #define clr clear 34 #define pb push_back 35 #define mp make_pair 36 #define fir first 37 #define sec second 38 #define all(x) (x).begin(),(x).end() 39 #define SZ(x) ((int)(x).size()) 40 #define lson l, mid, rt<<1 41 #define rson mid+1, r, rt<<1|1 42 43 typedef struct node_t { 44 int l, r, h; 45 46 node_t() {} 47 node_t(int l, int r, int h): 48 l(l), r(r), h(h) {} 49 50 friend bool operator< (const node_t& a, const node_t& b) { 51 return a.h > b.h; 52 } 53 54 } node_t; 55 56 const int maxn = 1005; 57 const int INF = 0x3f3f3f3f; 58 node_t nd[maxn]; 59 int dp[maxn][2]; 60 int n, x, y, mx, T; 61 62 void solve() { 63 bool fl, fr; 64 int tmp; 65 66 memset(dp, INF, sizeof(dp)); 67 dp[0][0] = dp[0][1] = 0; 68 rep(i, 0, n) { 69 #ifndef ONLINE_JUDGE 70 printf("l = %d, r = %d, [0] = %d, [1] = %d\n", nd[i].l, nd[i].r, dp[i][0], dp[i][1]); 71 #endif 72 fl = fr = true; 73 rep(j, i+1, n+1) { 74 tmp = nd[i].h - nd[j].h; 75 if (tmp > mx) 76 break; 77 if (fl && nd[j].l<=nd[i].l && nd[i].l<=nd[j].r) { 78 fl = false; 79 if (j == n) { 80 dp[j][0] = min(dp[j][0], dp[i][0]+tmp); 81 dp[j][1] = min(dp[j][1], dp[i][0]+tmp); 82 } else { 83 dp[j][0] = min(dp[j][0], dp[i][0]+tmp+nd[i].l-nd[j].l); 84 dp[j][1] = min(dp[j][1], dp[i][0]+tmp+nd[j].r-nd[i].l); 85 } 86 } 87 if (fr && nd[j].l<=nd[i].r && nd[i].r<=nd[j].r) { 88 fr = false; 89 if (j == n) { 90 dp[j][0] = min(dp[j][0], dp[i][1]+tmp); 91 dp[j][1] = min(dp[j][1], dp[i][1]+tmp); 92 } else { 93 dp[j][0] = min(dp[j][0], dp[i][1]+tmp+nd[i].r-nd[j].l); 94 dp[j][1] = min(dp[j][1], dp[i][1]+tmp+nd[j].r-nd[i].r); 95 } 96 } 97 } 98 } 99 100 if (dp[n][0]<=T || dp[n][1]<=T)101 puts("NO");102 else103 puts("YES");104 }105 106 int main() {107 ios::sync_with_stdio(false);108 #ifndef ONLINE_JUDGE109 freopen("data.in", "r", stdin);110 freopen("data.out", "w", stdout);111 #endif112 113 int t;114 115 scanf("%d", &t);116 while (t--) {117 scanf("%d %d %d %d %d", &n, &x, &y, &mx, &T);118 nd[0].l = nd[0].r = x;119 nd[0].h = y;120 rep(i, 1, n+1)121 scanf("%d %d %d", &nd[i].l, &nd[i].r, &nd[i].h);122 sort(nd, nd+n);123 ++n;124 nd[n].l = 0;125 nd[n].r = 1010;126 nd[n].h = 0;127 solve();128 }129 130 #ifndef ONLINE_JUDGE131 printf("time = %d.\n", (int)clock());132 #endif133 134 return 0;135 }
转载于:https://www.cnblogs.com/bombe1013/p/5086415.html