本来想着写一下滚动数组优化记录路径来着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.边和点可以互相转化
