这道题目是不太好想的，尽管很容易看出来应该是dp，但是状态转移总觉得无从下手。
其实我们可以将状态分层，比如设$dp(i, j)$为用$i$个路由器覆盖前$j$个点所需的最小代价
我们先不考虑状态，而是考虑在每个位置上的决策对状态的影响，考虑在位置j的决策
1.如果在此处放置网线，有$dp(i, j) = min(dp(i, j), dp(i, j - 1) + b(i))$
2.如果在此处放置路由器，有$dp(i, r(j)) = min(dp(i, r(j)), dp(i - 1, l(j) - 1) + a(i))$
当然此处可以什么都不放，但是这种决策对状态没有影响，因此我们不考虑它。
$[l(i), r(i)]$表示$i$位置路由器的覆盖区间
注意到固定$i$，$dp(i, j)$应该是非降的，因此条件2的更新应该适用于所有$dp(i, k): k leq r(j)$
用两重循环依次计算状态，用stl中的vector储存i位置满足$r(k) = i$的所有$k$，先用式2从后往前更新，再用式1从前往后更新即可
复杂度$O(n * max(k, log(n))$
代码如下：
1 #include <algorithm> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <queue> 6 #include <map> 7 #include <set> 8 #include <ctime> 9 #include <iostream> 10 using namespace std; 11 typedef long long ll; 12 const int int_inf = 0x3f3f3f3f; 13 const ll ll_inf = (ll)1 << 62; 14 const int mod = 1e9 + 7; 15 const double double_inf = 1e30; 16 typedef unsigned long long ul; 17 #define max(a, b) ((a) > (b) ? (a) : (b)) 18 #define min(a, b) ((a) < (b) ? (a) : (b)) 19 #define mp make_pair 20 #define st first 21 #define nd second 22 #define lson (u << 1) 23 #define rson (u << 1 | 1) 24 #define pii pair<int, int> 25 #define pb push_back 26 #define type(x) __typeof(x.begin()) 27 #define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++) 28 #define FOR(i, s, t) for(int i = s; i <= t; i++) 29 #define ROF(i, t, s) for(int i = t; i >= s; i--) 30 #define dbg(x) cout << x << endl 31 #define dbg2(x, y) cout << x << " " << y << endl 32 #define clr(x, i) memset(x, (i), sizeof(x)) 33 #define maximize(x, y) x = max((x), (y)) 34 #define minimize(x, y) x = min((x), (y)) 35 inline int readint(){ 36 bool neg = 0; char ch, t[11]; 37 int k = 0; 38 while((ch = getchar()) == ' ' || ch == ' ') ; 39 neg = ch == '-'; 40 ch == '-' ? neg = 1 : t[k++] = ch; 41 while((ch = getchar()) >= '0' && ch <= '9') t[k++] = ch; 42 int x = 0, y = 1; 43 while(k) x += (t[--k] - '0') * y, y *= 10; 44 return neg ? -x : x; 45 } 46 47 inline int readstr(char *s){ 48 char ch; 49 int len = 0; 50 while((ch = getchar()) == ' ' || ch == ' ') ; 51 *(s++) = ch, ++len; 52 while((ch = getchar()) != ' ' && ch != ' ') *(s++) = ch, ++len; 53 *s = ' '; 54 return len; 55 } 56 inline void writestr(const char *s){ 57 while(*s != ' ') putchar(*(s++)); 58 putchar(' '); 59 } 60 61 inline int add(int x, int y){ 62 if(x < 0) x += mod; 63 if(y < 0) y += mod; 64 return (x + y) % mod; 65 } 66 67 inline int mult(int x, int y){ 68 if(x < 0) x += mod; 69 if(y < 0) y += mod; 70 ll tem = (ll)x * y; 71 return tem % mod; 72 } 73 74 int debug = 0; 75 //------------------------------------------------------------------------- 76 const int maxn = 2e4 + 10; 77 int a[maxn], x[maxn], b[maxn], d[maxn]; 78 ll dp[105][maxn]; 79 vector<int> c[maxn]; 80 int l[maxn], r[maxn]; 81 int n, k; 82 //------------------------------------------------------------------------- 83 84 ll solve(){ 85 d[0] = d[1] = 0; 86 FOR(i, 2, n) d[i] += d[i - 1]; 87 FOR(i, 0, maxn - 1) c[i].clear(); 88 FOR(i, 1, n){ 89 int len = x[i]; 90 int L = 0, R = i; 91 while(R - L > 1){ 92 int mid = (R + L) >> 1; 93 if(d[i] - d[mid] <= len) R = mid; 94 else L = mid; 95 } 96 l[i] = R; 97 L = i, R = n + 1; 98 while(R - L > 1){ 99 int mid = (R + L) >> 1; 100 if(d[mid] - d[i] <= len) L = mid; 101 else R = mid; 102 } 103 r[i] = L; 104 c[L].pb(i); 105 } 106 dp[0][0] = 0; 107 FOR(i, 1, n) dp[0][i] = dp[0][i - 1] + b[i]; 108 FOR(i, 1, k){ 109 dp[i][n + 1] = ll_inf; 110 ROF(j, n, 1){ 111 int sz = c[j].size(); 112 dp[i][j] = dp[i][j + 1]; 113 FOR(u, 0, sz - 1) minimize(dp[i][j], dp[i - 1][l[c[j][u]] - 1] + a[c[j][u]]); 114 } 115 dp[i][0] = 0; 116 FOR(j, 1, n) minimize(dp[i][j], dp[i][j - 1] + b[j]); 117 } 118 ll ans = dp[0][n]; 119 FOR(i, 1, k) minimize(ans, dp[i][n]); 120 return ans; 121 } 122 123 int main(){ 124 /////////////////////////////////////////////////////////////////////////////////////////////////////////////// 125 if(debug) freopen("in.txt", "r", stdin); 126 int T = readint(); 127 while(T--){ 128 n = readint(); 129 k = readint(); 130 FOR(i, 1, n - 1) d[i + 1] = readint(); 131 FOR(i, 1, n) a[i] = readint(), x[i] = readint(), b[i] = readint(); 132 ll ans = solve(); 133 printf("%lld ", ans); 134 } 135 ////////////////////////////////////////////////////////////////////////////////////////////////////////////// 136 return 0; 137 }