本文共 1335 字，大约阅读时间需要 4 分钟。

here are n courses in the course selection system of Marjar University. The i-th course is described by two values: happiness H_i and credit C_i. If a student selects m courses x₁, x₂, ..., x_m, then his comfort level of the semester can be defined as follows:

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?

思路：这个题在秋天区域赛选拔赛的时候见过，这是第二次遇到这个题了，区域赛选拔赛的时候对这个题没什么思路，大概是赛后看了题解又觉得这个题太水了，没好好思考导致第二次遇到这个题竟然忘记怎么做了，到了最后的时刻还是队友突然想起来是一个背包，然后ac了。

本来以为是一个贪心，但是并没有找到什么贪心的策略，通过观察这个式子和数据范围我们会发现，c的值都很小，所以问题就可以转化为在相同c的取值下，能够取到的最大的h的和是多少，这样我们就可以很容易的想到背包了。

#include 
   
    #include 
    
     using namespace std;const int maxn=50050;long long  int dp[maxn];int n;struct Node{    int h,c;} node[maxn];long long int dig(long long int h,long long  int c){    return h*h-h*c-c*c;}int main(){    int T;    scanf("%d",&T);    while(T--)    {        scanf("%d",&n);        int m=0;        for(int i=0; i
     
      =0; j--)            {                if(j>=node[i].c)                {                    dp[j]=max(dp[j],dp[j-node[i].c]+node[i].h);                }            }        }        long long   int ans=0;        for(int i=0; i<=m; i++)        {            ans=max(ans,dig(dp[i],i));        }        cout<
      
       <
      
     
    
   

转载地址：http://fbgsi.baihongyu.com/