题面好难找：嘟嘟嘟
贪心 + dp。
首先要按bi的降序排序，让每一次减少大的数尽量靠前。为啥咧？于是我们就需要证明：令sum = a1 - (1 - 1) * b1 + a2 - (2 - 1) * b2 + a3 - (3 - 1) * b3 + ……+ an - (n - 1) * bn，整理得：sum = (a1 + a2 + a3 + ……+ an) + (0 * b1 + 1 * b2 + 2 * b3 + ……+ (n - 1) * bn)。因为Σan是定值，所以让sum最大就是让bi降序排序。
然后dp。
令dp[i][j]第 j 回合取ai的最大得分，仿照01背包：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + a[i] - (j - 1) * b[i])。
于是这道题就做完啦。
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<vector> 9 #include<stack> 10 #include<queue> 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a, x) memset(a, x, sizeof(a)) 15 #define rg register 16 typedef long long ll; 17 typedef double db; 18 const int INF = 0x3f3f3f3f; 19 const db eps = 1e-8; 20 const int maxn = 205; 21 inline ll read() 22 { 23 ll ans = 0; 24 char ch = getchar(), last = ' '; 25 while(!isdigit(ch)) {last = ch; ch = getchar();} 26 while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();} 27 if(last == '-') ans = -ans; 28 return ans; 29 } 30 inline void write(ll x) 31 { 32 if(x < 0) x = -x, putchar('-'); 33 if(x >= 10) write(x / 10); 34 putchar(x % 10 + '0'); 35 } 36 37 int n, m; 38 struct Node 39 { 40 int a, b; 41 bool operator < (const Node &oth)const 42 { 43 return b > oth.b; 44 } 45 }t[maxn]; 46 ll dp[maxn][maxn]; 47 48 int main() 49 { 50 n = read(); m = read(); 51 for(int i = 1; i <= n; ++i) t[i].a = read(); 52 for(int i = 1; i <= n; ++i) t[i].b = read(); 53 sort(t + 1, t + n + 1); 54 for(int i = 1; i <= n; ++i) 55 for(int j = 1; j <= m; ++j) 56 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + t[i].a - (j - 1) * t[i].b); 57 write(dp[n][m]), enter; 58 return 0; 59 }