There 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?
There 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++.
For each case, you should output one integer denoting the maximum comfort.
2
3
10 1
5 1
2 10
2
1 10
2 10191
0For the first case, Edward should select the first and second courses.
For the second case, Edward should select no courses.
[button color="success" url="https://vjudge.net/problem/ZOJ-3956" outline="default" target="_blank"]vjudge_ZOJ-3956-Course Selection System[/button]
通过题目我们可以了解到在一定的$C$下$H$越高，$comfort level$就越高，所以我们应该求出在所有可能的$C$值下最高的$H$值，因为$C$的最大值并不大，题目给出不超过$5000$；因此我们可以创建一个数组来进行0/1背包的求解。求出每个$C$下最高的$H$，注意$H$的范围，所以int的范围是不够表达comfortable的值的，要用long long int,求出所有最高$H$后再进行计算，求出所有$C$中的最优解。
#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;
}ACM (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$)?
There 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}$.
For 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.
2
10 3 3 2
1 3
5 8
10 10
1 8
10 10
5 3 1 1
1 2
4 53
0For 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$.
[button color="success" url="https://vjudge.net/problem/ZOJ-3962" outline="default" target="_blank"]vjudge_ZOJ-3961-Let's Chat[/button]
一个求交集的问题，把区间表示出来就好
#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;
}