hdu 2191単調キュー最適化


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のコード:
#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; }