本题是燕老师&林队&WMY的七拼八凑赛的 (mathrm{T3}).
搬运自我的洛谷博客
Orz 隔壁机房杜爷首 A & 最优解
(mathrm{Orz space qwaszx、eee})(mathrm{hoho、dozenX、Tian})(mathrm{Xing、zrzring space 5}) 位大佬 (mathrm{AC space \% \% \%})
为了证明自己是个良心出题人，(mathrm{lxy}) 出了这样一道签到题。
5pts
人口普查。
#include <iostream>
using namespace std;
int main()
{
cout << "171128";
return 0;
}
40pts
打一个暴力就能过。
至于这个暴力怎么打，(mathrm{lxy}) 小菜鸡也没有试过，这个问题要去问燕老师。下面我们跳过解析过程，来欣赏一下燕老师优美的暴力：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 604
using namespace std;
int n,T,t[N],val[N],x,y,lo,dp[N][N];
int d[N],ans=0,dmax;
bool mark[N];
void dfs(int i,int time,int weight){
if(time>T)return;
if(weight+dp[1][T-time]<ans) //神仙的剪枝
return;
ans=max(ans,weight);
for(int a=1;a<=n;a++){
if(!mark[a]){
mark[a]=true;
dfs(i+1,time+t[a],weight+d[i]*val[a]);
mark[a]=false;
}
}
}
int main(){
cin>>n>>T;
for(int a=1;a<=n;a++){
cin>>x>>y>>t[a];
val[a]=y*10+x;
}
for(int a=1;a<=n;a++)
cin>>d[a],dmax=max(dmax,d[a]);
for(int a=n;a>=1;a--){
for(int b=0;b<t[a];b++)
dp[a][b]=dp[a+1][b];
for(int b=t[a];b<=T;b++)
dp[a][b]=max(dp[a+1][b],dp[a+1][b-t[a]]+val[a]*dmax);
}
dfs(1,0,0);
cout<<ans;
return 0;
}
40 + 20pts
(d_i = 1)，相当于数列 (d) 不存在，这不就是 (01) 背包模板吗...
照着“采药”那道题改一下即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1001;
int n, T, ans = 0, a[N], b[N], w[N], d[N], val[N], f[N][N];
int main()
{
scanf("%d%d", &n, &T);
swap(n, T);
for(int i = 1; i <= n; i++)
{
scanf("%d%d%d", &a[i], &b[i], &w[i]);
val[i] = b[i] * 10 + a[i];
//cin >> w[i] >> val[i];
}
//for(int i = 1; i <= n; i++) d[i] = 1;
for(int i = 1; i <= n; i++) scanf("%d", &d[i]);
memset(f, 0, sizeof(f));
for(int i = 1; i <= n; i++)
for(int k = T; k >= w[i]; k--)
for(int j = 1; j <= i; j++)
f[j][k] = max(f[j][k], f[j - 1][k - w[i]] + val[i] * d[j]),
ans = max(ans, f[j][k]);
printf("%d", ans);
return 0;
}
100pts
普通的 (01) 背包好像不行了，可不可以在模板的基础上稍作改动呢？
假设我们已经选择了 (i) 个物品 (s_1, s_2, s_3...s_i)，这些物品的体积已经确定了，我们现在需要确定的是它们的排放顺序。有一个很显然的贪心，那就是用较大的 (d_i) 与较大的 (val_i) 相乘，以获得最大价值。
考虑把这个过程融入到 (mathrm{dp}) 中：
首先，由于物品的先后顺序不影响背包过程，先对物品按照 (val) 从大到小进行排序
那么接下来可不可以对 (d) 排序，然后跑一个 (01) 背包呢？答案是不行。如果我们在 (n) 个物品中只选择了 (m) 个，而 (d_i) 的范围是 (1-n)，这时候多出来的 (d_j) ((m<j leq n)) 将会干扰答案。
所以我们考虑一个更为暴力的做法：枚举 (m)，对前 (m) 个 (d_i) 排序，再进行一个类似于多维背包的 (mathrm{dp}).
具体来说，设 (f_{i,j}) 表示已经选了 (i) 个物品，体积为 (j) 的最大价值，(mathrm{dp}) 部分代码如下：
for(int i = 1; i <= n; i++) //枚举物品
for(int k = T; k >= s[i].w; k--) //枚举体积
for(int j = 1; j <= min(num, i); j++) //枚举当前选的是第几个
f[j][k] = max(f[j][k], f[j - 1][k - s[i].w] + s[i].val * g[j]); //g是排序后的d
注意，最终我们需要的是恰好取 (m) 个物品的价值，所以背包需要初始化为极小值。时间复杂度 (mathrm{O(n^3T)})
最后放上垃圾的代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 233333;
struct node { int w, val; } s[N];
int n, T, ans = 0, a[N], b[N], d[N], g[N], f[233][233];
bool cmp(node a, node b) { return a.val > b.val; }
bool cmp2(int a, int b) { return a > b; }
signed main()
{
scanf("%lld%lld", &n, &T);
for(int i = 1; i <= n; i++)
{
scanf("%lld%lld%lld", &a[i], &b[i], &s[i].w);
s[i].val = b[i] * 10 + a[i];
}
for(int i = 1; i <= n; i++) scanf("%lld", &d[i]);
sort(s + 1, s + n + 1, cmp);
for(int num = 1; num <= n; num++)
{
for(int i = 1; i <= num; i++) g[i] = d[i];
sort(g + 1, g + num + 1, cmp2);
memset(f, -0x7f7f7f, sizeof(f));
f[0][0] = 0;
for(int i = 1; i <= n; i++)
for(int k = T; k >= s[i].w; k--)
for(int j = 1; j <= min(num, i); j++)
f[j][k] = max(f[j][k], f[j - 1][k - s[i].w] + s[i].val * g[j]);
for(int i = 0; i <= T; i++) ans = max(ans, f[num][i]);
}
printf("%lld", ans);
return 0;
}
UPDATE
好多大佬都在卡最优解啊...
放一个卡常数版本的被吊打的标程吧
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define re register
using namespace std;
const int N = 233;
struct node { LL w, val; } s[N], h[N];
LL n, T, tot = 0, sum = 0, ans = 0, a[N], b[N], d[N], g[N], f[102][102]; //因为需要 memset，f数组开小一点
bool cmp(node a, node b) { return a.val > b.val; }
bool cmp2(LL a, LL b) { return a > b; }
bool cmp3(node a, node b) { return a.w < b.w; }
int main()
{
scanf("%lld%lld", &n, &T);
for(re int i = 1; i <= n; i++)
{
scanf("%lld%lld%lld", &a[i], &b[i], &s[i].w);
s[i].val = b[i] * 10 + a[i];
}
for(re int i = 1; i <= n; i++) h[i] = s[i];
for(re int i = 1; i <= n; i++) scanf("%lld", &d[i]);
sort(s + 1, s + n + 1, cmp);
sort(h + 1, h + n + 1, cmp3); //数据很水，加这个优化快了很多QWQ
for(re int i = 1; i <= n; i++) { if(sum + h[i].w > T) break; sum += h[i].w, tot++; }
for(re int num = 1; num <= tot; num++)
{
g[num] = d[num]; //卡常数，避免重新复制一遍
sort(g + 1, g + num + 1, cmp2);
memset(f, -0x7f7f7f, sizeof(f));
f[0][0] = 0;
for(re int i = 1; i <= n; i++)
for(re int k = T; k >= s[i].w; k--)
for(re int j = 1; j <= min(num, i); j++)
f[j][k] = max(f[j][k], f[j - 1][k - s[i].w] + s[i].val * g[j]);
for(re int i = 0; i <= T; i++) ans = max(ans, f[num][i]);
}
printf("%lld", ans);
return 0;
}