hdu 2191単調キュー最適化
1250 ワード
F[i][j] = max { F[i] - 1) [j] – k * v[i] ] + k * w[i] } (0 <= k <= m[i] シンプルな多重バックパックの転送式です.
v[i]を容量と仮定する. w[i]の価値 no[i]は数量です
a=j/v[i]つまりaはi種のものの最大使用可能回数です. b=j%v[i]はi種のものでは表現できない価値です.
質素転送式は、F[i][j]=max{F[a*v][i]+b-k*v[i]+(a-k)*w[i]とすることができます. }
a-kの代わりにkを使う 得F[i][j]=max{F[i-1][k*v[i]+b]-k*[w] } + a*w[i] ここで(k:0-->j/a)
単調な列はF[i]、[j]-a**w[i]の一番の値を計算するものです.
hdu 2191のコード:
v[i]を容量と仮定する. w[i]の価値 no[i]は数量です
a=j/v[i]つまりaはi種のものの最大使用可能回数です. b=j%v[i]はi種のものでは表現できない価値です.
質素転送式は、F[i][j]=max{F[a*v][i]+b-k*v[i]+(a-k)*w[i]とすることができます. }
a-kの代わりにkを使う 得F[i][j]=max{F[i-1][k*v[i]+b]-k*[w] } + a*w[i] ここで(k:0-->j/a)
単調な列はF[i]、[j]-a**w[i]の一番の値を計算するものです.
hdu 2191のコード:
#include
#include
using namespace std;
typedef struct
{
int x,t;
}Q;
int f[110];
int v[110],w[110],no[110];
Q ux[110];
int n,m;
int fabs(int x)
{
if(x<0) return -x;
return x;
}
int main()
{
int ti;
int s,t;
scanf("%d",&ti);
while(ti--)
{
scanf("%d%d",&n,&m);
for(int i=0;ino[i]&&s<=t) s++;
f[j+k*v[i]]=ux[s].x+k*w[i];
}
}
}
printf("%d
",f[n]);
}
return 0;
}