4.22 study record (you only did water problems in one day, didn't you)

Originally I wanted to write a rolling array to optimize the record path qwq, It didn't come out
P1417 Cooking plan
Greedy optimization + knapsack

The problem was complicated at first , Looks like DP There's also DP（ dynamic DP Dabao ）, So I want to optimize it with greed , I bet that there is no case where the attenuation value is negative （ The longer it lasts, the more fragrant it becomes ） So we happily made it with backpacks

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define N 55

struct Obj
{
    
    long long a,b,c;
};
Obj obj[N];
long long dp[N*100000];
bool cmp(Obj x,Obj y)
{
    
    return x.c*y.b<y.c*x.b;
}
int main()
{
    
    //freopen("in.txt","r",stdin);
    long long t,n;
    cin>>t>>n;
    for(int i=1;i<=n;i++)
        cin>>obj[i].a;
    for(int i=1;i<=n;i++)
        cin>>obj[i].b;
    for(int i=1;i<=n;i++)
        cin>>obj[i].c;
    sort(obj+1,obj+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
    
        for(int j=t;j>=obj[i].c;j--)
        {
    
            dp[j]=max(dp[j],dp[j-obj[i].c]+obj[i].a-j*obj[i].b);
        }
    }
    long long ans=-1;
    for(int i=1;i<=t;i++)
    {
    
        ans=max(dp[i],ans);
    }
    cout<<ans<<endl;
    return 0;
}

CF Div4 The topic ,, Although I feel there is nothing to sort out , Or write a H Let's write it down , After all, it's been a long time div4
H. Maximal AND
difficulty ： Visual measurement 800
The question ： For an array, you can choose one number at a time 30 Binary bits within bits 0 change 1,1 change 0, most k Time , Ask you the of the whole array & What is the maximum result of the operation

Ideas ： Greedy for water

#include <bits/stdc++.h>
using namespace std;
int main()
{
    
   int t;
   for(cin>>t;t;t--)
   {
    
       int n,k;
       cin>>n>>k;
       int a[40]={
    0};
       for(int i=1;i<=n;i++)
       {
    
           int tmp;
           cin>>tmp;
           for(int i=0;i<=30;i++)
               a[i]++;
           int con=0;
           while(tmp)
           {
    
               if(tmp&1)
                   a[con]--;
               con++;
               tmp>>=1;
           }
       }
       int ans=0;
        for(int i=30;i>=0;i--)
        {
    
            if(a[i]<=k)
            {
    
                ans+=1<<i;
                k-=a[i];
            }
        }
        cout<<ans<<endl;
   }
}
 

Today, after reviewing the tree backpack, I have a new understanding
1. Tree knapsack actually uses the idea of grouping knapsack
2. Tree backpacks usually have a situation

DFS(int now,int fath)
{
    
   for(int i=head[now];i;i=edge[i].nex)
   {
    
       DP[now][1]=w[now];// Assign initial value to 
       DFS(edge[i].to,now);
       for(int j=m+1;j>=1;j--)//m+1 Because virtual nodes are generated 
       {
    
          for(int k=j-1;k>=0;k--)
          {
    
             dp[now][j]=max(dp[now][j],dp[now][j-k]+dp[edge[i].to][k]);
          }
       }
   }
}

3. Edges and points can be transformed into each other