当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

POJ1276

发表于: 2013-05-16   作者:EmmaZhao   来源:转载   浏览次数:
poj
摘要: #include<iostream> using namespace std; int main() { int cash,n,max; while(cin>>cash>>n) { max = 0; int m[1001],v[1001]; for(int i = 0;i<n;i++) cin>>m[
#include<iostream>
using namespace std;

int main()
{
	int cash,n,max;
	while(cin>>cash>>n)
	{
		max = 0;
		int m[1001],v[1001];
		for(int i = 0;i<n;i++) cin>>m[i]>>v[i];

		bool dp[100001];
		memset(dp,0,sizeof(dp));
		dp[0] = true;
		for(int i = 0;i<n;i++)
		{
			for(int j = max;j>=0;j--)
			{
				if(dp[j])
				{
					for(int k = 1;k <= m[i];k++)
					{
						int tmp = j+k*v[i];
						if(tmp>cash) break;
						dp[tmp] = true;
						if(tmp>max) max = tmp;
					}
				}
			}
		}
		cout<<max<<endl;
	}
	return 0;
}

POJ1276

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号