(TOJ) 157 [rolling hash]

http://sprout.tw/oj/pro/157/

一定要用rolling hash!!!

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;

int a[2][1000001];
int w[101];
int v[101];

int main () {
int T;
scanf("%d",&T);
while (T--) {
int n,m;
scanf("%d %d",&n,&m);
for (int x=1;n>=x;x++) scanf("%d %d",&w[x],&v[x]);
memset(a,0,sizeof(a));
for (int x=1;n>=x;x++) {
for (int y=1;m>=y;y++) {
if (y - w[x] < 0) a[1][y] = a[0][y];
else a[1][y] = max(a[0][y],a[0][y-w[x]] + v[x]);
}
for (int y=1;m>=y;y++) a[0][y] = a[1][y];
}
printf("%d\n",a[1][m]);
}
}