人才网站怎么建设,衡量一个网站的指标,wordpress 中文模板,小程序源码提取problem
luogu
你有 nnn 个箱子#xff0c;编号从 1 到 n#xff0c;每个箱子有三个属性#xff0c;以第 iii 个箱子为例#xff0c;分别是重量 wiw_iwi#xff0c;承重能力 sis_isi#xff0c;价值 viv_ivi。
你想建一座塔#xff0c;因此需要将一些箱子堆叠起…problem
luogu
你有 nnn 个箱子编号从 1 到 n每个箱子有三个属性以第 iii 个箱子为例分别是重量 wiw_iwi承重能力 sis_isi价值 viv_ivi。
你想建一座塔因此需要将一些箱子堆叠起来但是每个箱子必须满足下面的条件
这个箱子上面的所有箱子重量和要小于这个箱子的承重能力。
定义一个塔的价值为它所用的所有箱子的价值和。
最大化这个塔的价值并输出它。
solution
这种前后两个顺序有优劣差别但不会影响除两个物品外的其余物品每个物品具有多个属性的题目。
往往需要进行局部最优性的属性排序然后再做一遍背包即可。
这里考虑相邻的两个物品 i,ji,ji,j。
设前面物品的总重量为 WWW显然这两个的顺序不会影响后面物品的摆放。
假设 iii 必须放在 jjj 前面才行。
则有 Wwj≤si∧sjWwiWw_j\le s_i\wedge s_jWw_iWwj≤si∧sjWwi两式相加有 wjsjwisiw_js_jw_is_iwjsjwisi。
所以将所有物品按 swswsw 排序后做一遍背包即可。
code
#include bits/stdc.h
using namespace std;
#define int long long
int f[1005][20005];
int n;
struct node { int w, s, v; }it[1005];
signed main() {scanf( %lld, n );for( int i 1;i n;i ) scanf( %lld %lld %lld, it[i].w, it[i].s, it[i].v );sort( it 1, it n 1, [](node x, node y ){ return x.w x.s y.w y.s; } );for( int i 1;i n;i )for( int j 0;j 2e4;j ) {if( j it[i].s ) f[i 1][j it[i].w] max( f[i 1][j it[i].w], f[i][j] it[i].v );f[i 1][j] max( f[i 1][j], f[i][j] );}int ans 0;for( int i 0;i 2e4;i ) ans max( ans, f[n 1][i] );printf( %lld\n, ans );return 0;
}
