4.22学习记录（你一天只做了水题是吗）

本来想着写一下滚动数组优化记录路径来着qwq，结果没写出来
P1417 烹调方案
贪心优化+背包

这题刚开始觉得很复杂，貌似DP里还有DP（动态DP达咩），所以想着用贪心优化一下，赌了一把这题里面没有衰减值为负值的情况（就是越久越香）所以我们就愉快地用背包做出来了

#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的题，，虽然感觉通篇没有什么好整理的，还是写个H题记录一下吧，毕竟好久才来一次div4
H. Maximal AND
难度：目测 800
题意：对一个数组你可以每次选一个数的30位以内的二进制位0变1，1变0，最多k次，问你整个数组的&运算结果最大为多少

思路：贪心水题

#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;
   }
}
 

今天回顾了树形背包之后有了新的理解
1.树形背包实际上用的是分组背包的思想
2.树形背包一般都有一下形势

DFS(int now,int fath)
{
    
   for(int i=head[now];i;i=edge[i].nex)
   {
    
       DP[now][1]=w[now];//赋初值
       DFS(edge[i].to,now);
       for(int j=m+1;j>=1;j--)//m+1是因为生成了虚节点
       {
    
          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.边和点可以互相转化