BZOJ 1531: [POI2005]Bank notes

按余数分类

单调队列优化

#include<cstdio>

using namespace std;

int n,m,b[205],c[205],F[20005];

struct node{

	int fr,sc;

}q[20005];

int main(){

	scanf("%d",&n);

	for (int i=1; i<=n; i++) scanf("%d",&b[i]);

	for (int i=1; i<=n; i++) scanf("%d",&c[i]);

	scanf("%d",&m);

	for (int i=1; i<=20000; i++) F[i]=1e9;

	for (int i=1; i<=n; i++){

		for (int d=0; d<b[i]; d++){

			int head=1,tail=0;

			for (int j=0; b[i]*j+d<=m; j++){

				int now=b[i]*j+d;

				while (head<=tail && q[tail].sc>=F[now]-j) tail--;

				q[++tail]=(node){j,F[now]-j};

				while (head<=tail && q[head].fr<j-c[i]) head++;

				F[now]=1e9;

				if (head<=tail) F[now]=q[head].sc+j;

			}

		}

	}

	printf("%d\n",F[m]);

	return 0;

}