记录编号	43930	评测结果	AAAAAAAAAA
题目名称	智力大冲浪	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.026 s
提交时间	2012-10-15 15:22:22	内存使用	4.14 MiB

#include <iostream>
#include <cstdio>
using namespace std;

int a[510],b[510],f[510][510];

void swap(int& a,int& b)
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}

int main(void)
{
	freopen("riddle.in","r",stdin);
	freopen("riddle.out","w",stdout);
	int i,j,m,n,total=0,maxget=0;
	cin>>m>>n;
	for (i=1;i<=n;i++)
		cin>>a[i];
	for (i=1;i<=n;i++)
	{
		cin>>b[i];
		total+=b[i];
	}
	
	/*pop sort*/
	for (i=1;i<n;i++)
		for (j=1;j<=n-i;j++)
			if (a[j]>a[j+1])
			{
				swap(a[j],a[j+1]);
				swap(b[j],b[j+1]);
			}
	/*pop sort*/
	
	/*DP*/
	for (i=1;i<=n;i++)
	{
		f[i][0]=f[i-1][0]+b[i]*(a[i]>=i);
		for (j=1;j<i;j++)
		{
            f[i][j]=f[i-1][j]+b[i]*(a[i]>=i-j);
            if (f[i][j]<f[i-1][j-1])
                f[i][j]=f[i-1][j-1];
			if (maxget<f[i][j])
				maxget=f[i][j];
		}
	}
	/*DP*/
	
	cout<<m-(total-maxget)<<endl;
	return(0);
}