https://www.lbxpace.com/index.php/tag/Thinking/ https://www.lbxpace.com/index.php/archives/23/ 2023-08-30T16:19:00+08:00 Problem DescriptionThere are $n$ courses in the course selection system of Marjar University. The $i$-th course is described by two values: happiness $Hi$ and credit $Ci$. If a student selects $m$ courses $x1$, $x2$, ..., $xm$, then his comfort level of the semester can be defined as follows:$$(\sum^m_{i=1}H_{x_i})^2-(\sum^m_{i=1}H_{x_i})\times (\sum^m_{i=1}C_{x_i})-(\sum^m_{i=1}C_{x_i})^2$$Edward, a student in Marjar University, wants to select some courses (also he can select no courses, then his comfort level is $0$) to maximize his comfort level. Can you help him?InputThere are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:The first line contains a integer $n$ $(1 ≤ n ≤ 500)$ -- the number of cources.Each of the next $n$ lines contains two integers $H_i$ and $C_i$ $(1 ≤ H_i ≤ 10000, 1 ≤ C_i ≤ 100)$.It is guaranteed that the sum of all $n$ does not exceed $5000$.We kindly remind you that this problem contains large I/O file, so it's recommended to use a faster I/O method. For example, you can use scanf/printf instead of cin/cout in C++.OutputFor each case, you should output one integer denoting the maximum comfort.Sample Input2 3 10 1 5 1 2 10 2 1 10 2 10Sample Output191 0HintFor the first case, Edward should select the first and second courses.For the second case, Edward should select no courses.Problem Link[button color="success" url="https://vjudge.net/problem/ZOJ-3956" outline="default" target="_blank"]vjudge_ZOJ-3956-Course Selection System[/button]Thought通过题目我们可以了解到在一定的$C$下$H$越高，$comfort level$就越高，所以我们应该求出在所有可能的$C$值下最高的$H$值，因为$C$的最大值并不大，题目给出不超过$5000$；因此我们可以创建一个数组来进行0/1背包的求解。求出每个$C$下最高的$H$，注意$H$的范围，所以int的范围是不够表达comfortable的值的，要用long long int,求出所有最高$H$后再进行计算，求出所有$C$中的最优解。Code#include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> # define MaxN 500+5 # define MaxC 500*100+5 typedef long long int LL; LL max(LL a,LL b) { return a>b ? a:b; } int main() { int T; scanf("%d",&T); while(T--) { int dp[MaxC]; int H[MaxN]; int C[MaxN]; memset(dp,0,sizeof dp); int N; int i; int TopC=0; scanf("%d",&N); for(i=1;i<=N;i++) { scanf("%d",&H[i]); scanf("%d",&C[i]); TopC+=C[i]; } for(i=1;i<=N;i++) { int l; for(l=TopC;l>=C[i];--l) dp[l]=max(dp[l],dp[l-C[i]]+H[i]); } LL max1=0; for(i=0;i<=TopC;i++) max1=max(1LL*dp[i]*dp[i]-1LL*dp[i]*i-1LL*i*i,max1); printf("%lld",max1); if(T!=0) printf("\n"); } return 0; } https://www.lbxpace.com/index.php/archives/22/ 2023-08-30T13:22:00+08:00 Problem DescriptionACM (ACMers' Chatting Messenger) is a famous instant messaging software developed by Marjar Technology Company. To attract more users, Edward, the boss of Marjar Company, has recently added a new feature to the software. The new feature can be described as follows:If two users, $A$ and $B$, have been sending messages to each other on the last m consecutive days, the "friendship point" between them will be increased by $1$ point.More formally, if user A sent messages to user B on each day between the $(i - m + 1)$-th day and the $i$-th day (both inclusive), and user $B$ also sent messages to user $A$ on each day between the $(i - m + 1)$-th day and the $i$-th day (also both inclusive), the "friendship point" between $A$ and $B$ will be increased by $1$ at the end of the i-th day.Given the chatting logs of two users $A$ and $B$ during $n$ consecutive days, what's the number of the friendship points between them at the end of the $n$-th day (given that the initial friendship point between them is $0$)?InputThere are multiple test cases. The first line of input contains an integer $T$ $(1 ≤ T ≤ 10)$, indicating the number of test cases. For each test case:The first line contains $4$ integers $n$ $(1 ≤ n ≤ 10^9)$, $m$ $(1 ≤ m ≤ n)$,$x$ and $y$ $(1 ≤ x, y ≤ 100)$. The meanings of $n$ and $m$ are described above, while $x$ indicates the number of chatting logs about the messages sent by $A$ to $B$, and $y$ indicates the number of chatting logs about the messages sent by $B$ to $A$.For the following $x$ lines, the $i$-th line contains $2$ integers $l_{a, i}$ and $r_{a, i} (1 ≤ l_{a, i} ≤ r_{a, i} ≤ n)$, indicating that $A$ sent messages to $B$ on each day between the $l_{a, i}$-th day and the $r_{a, i}$-th day (both inclusive).For the following $y$ lines, the $i$-th line contains $2$ integers $l_{b, i}$ and $r_{b, i} (1 ≤ l_{b, i} ≤ r_{b, i} ≤ n)$, indicating that $B$ sent messages to $A$ on each day between the $l_{b, i}$-th day and the $r_{b, i}$-th day (both inclusive).It is guaranteed that for all $1 ≤ i < x$, $r_{a, i} + 1 < l_{a, i+1} $ and for all $1 ≤ i < y, r_{b, i} + 1 < l_{b, i + 1}$.OutputFor each test case, output one line containing one integer, indicating the number of friendship points between $A$ and $B$ at the end of the $n$-th day.Sample Input2 10 3 3 2 1 3 5 8 10 10 1 8 10 10 5 3 1 1 1 2 4 5Sample Output3 0HintFor the first test case, user $A$ and user $B$ send messages to each other on the $1st$, $2nd$, $3rd$, $5th$, $6th$, $7th$, $8th$ and $10th$ day. As $m = 3$, the friendship points between them will be increased by $1$ at the end of the $3rd$, $7th$ and $8th$ day. So the answer is $3$.Problem Link[button color="success" url="https://vjudge.net/problem/ZOJ-3962" outline="default" target="_blank"]vjudge_ZOJ-3961-Let's Chat[/button]Thoughts一个求交集的问题，把区间表示出来就好Code#include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #define MAX 100+10 typedef long long LL; struct cbc { LL l,r; }AtoB[MAX],BtoA[MAX]; LL max(LL a,LL b) { return a>b ? a:b; } LL min (LL a,LL b) { return a<b? a:b; } int main() { int T; scanf("%d",&T); while(T--) { LL N; int m,x,y; int friendshippoint=0; scanf("%lld%d%d%d",&N,&m,&x,&y); int i; for(i=0;i<x;i++) scanf("%lld%lld",&AtoB[i].l,&AtoB[i].r); for(i=0;i<y;i++) scanf("%lld%lld",&BtoA[i].l,&BtoA[i].r); for(i=0;i<x;i++) { int i1; for(i1=0;i1<y;i1++) { int l,r; l=max(AtoB[i].l,BtoA[i1].l); r=min(AtoB[i].r,BtoA[i1].r); if(l>r || r-l+1<m) continue; else friendshippoint+=r-l+1-m+1; } } printf("%d\n",friendshippoint); } return 0; }