洛谷 U19159 采摘毒瘤

题目背景

Salamander见到路边有如此多的毒瘤，于是见猎心喜，从家里拿来了一个大袋子，准备将一些毒瘤带回家。

题目描述

路边共有 $种毒瘤有k_i 个，每个需要占据d_i 的空间。Salamander的袋子能装下的最大体积为m 。$

Salamander是一个很贪心的人，不过他也不要求带尽可能多或是总体积尽可能大的毒瘤回家，他只要求袋子里再也装不下剩余的任何一种毒瘤。

Salamander想知道有多少种不同的装毒瘤的方案。两种方案不同当且仅当取的毒瘤种类不同或者至少有一种毒瘤取的数量不同。由于方案数可能太多，请输出答案对

输入输出格式

输入格式：

第一行包括两个正整数

接下来的 $行，每行两个正整数k_i 、d_i ，表示一种毒瘤。$

输出格式：

一行，表示不同的方案数对

输入输出样例

输入样例#1：

2 5
2 3
3 1

输出样例#1：

说明

样例解释：

两种方案如下：

1.取1个第一种毒瘤和2个第二种毒瘤。

2.取3个第二种毒瘤。

对于10%的数据， $n,k_i,d_ileq 101≤n,ki,di≤10 ，1leq mleq 1001≤m≤100 ；$

对于30%的数据， $n,k_i,d_ileq 501≤n,ki,di≤50 ，1leq mleq 50001≤m≤5000 ；$

对于另外20%的数据， $k_i=1ki=1 ；$

对于100%的数据， $n,k_i,d_ileq 5001≤n,ki,di≤500 ，1leq mleq 10^5。$

#include<bits/stdc++.h>
#define ll long long
#define maxn 100005
using namespace std;
const int ha=19260817;
int f[2][maxn],n,m;
int V,tot,sum;
struct node{
	int v,num;
	bool operator <(const node &u)const{
		return v<u.v;
	}
}a[505];
int ans=0;

inline int add(int x,int y){
	x+=y;
	if(x>=ha) x-=ha;
	return x;
}

inline int X(int x,int y){
	x-=y;
	if(x<0) x+=ha;
	return x;
}

int main(){
	scanf("%d%d",&n,&V);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i].num,&a[i].v);
		tot+=a[i].num*a[i].v;
	}
	sort(a+1,a+n+1);
	
	if(tot<=V){
		puts("1");
		return 0;
	}
	
	f[0][0]=1;
	int now=0,pre;
	for(int i=n;i;i--){
		tot-=a[i].num*a[i].v;
		pre=now,now^=1;
		
		int base=a[i].v,len=base*a[i].num;
		
		for(int j=0;j<base;j++){
			sum=0;
		    for(int u=j;u<=V;u+=base){
		    	sum=add(sum,f[pre][u]);
		    	if(u-j>=len) sum=X(sum,f[pre][u-len]);
		    	f[now][u]=sum;
			}
		}
		
		int tp=V-tot;
		for(int j=max(0,tp-a[i].v+1);j<=tp;j++) ans=add(ans,f[now][j]);
		for(int j=len;j<=V;j++) f[now][j]=add(f[now][j],f[pre][j-len]);
	}
	
	printf("%d
",ans);
	return 0;
}