P2871 [USACO07DEC]手链Charm Bracelet数据太水

看起来二维空间会MLE
实际上只需要设成short类型就可以AC

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int ci,wi;
};
node a[3500];
short f[3500][12900];
int main()
{
	int n,m;
	memset(a,0,sizeof(a));
	cin >> n >> m;
	for (int i=1;i<=n;i++)
	  {
	  	cin >> a[i].ci >> a[i].wi;
	  }
	 for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            {
                if (a[i].ci<=j)
                  {
                  	f[i][j] = max(int(f[i-1][j]),int(f[i-1][j-a[i].ci]+a[i].wi));
				  }
                else 
				  {
				  	f[i][j] = f[i-1][j];
				  }
            }
    cout << f[n][m] << endl;
	return 0;
}