我反正是想不到。这个是我在他基础上改的：94msAC

#include <iostream>
using namespace std;
const int N=200001, MID = 100000;
int n, a, b, l, r, dp[N];//dp的角标代表sumS，值代表sumF
int main()
{
	dp[MID] = MID;//a=0, b=0
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
		scanf("%d %d", &a, &b);
		l = MID-1000*(i-1)+a;//优化迭代区间
		r = MID+1000*(i-1)+a;
		if(a > 0)
		{
			for(int j = r; j >= l; j--)//a > 0 就从反向迭代
				if(dp[j-a] || dp[j])
					dp[j] = max(dp[j], dp[j-a]+b);
		}
		else
		{
			for(int j = l; j <= r; j++)
				if(dp[j-a] || dp[j])
					dp[j] = max(dp[j], dp[j-a]+b);
		}
	}
	int ans = 0;
	for(int i = MID; i < N; i++)//dp[i]在这个区间存在，sumS >= 0
		if(dp[i] && dp[i] >= MID)//&& sumF >= 0
			ans = max(ans, i-MID+dp[i]-MID);
	printf("%d\n", ans);
	return 0;
}

• 额。。那你是怎么做的？我也只想到这个做法，另外这个算dp么。。感觉只是暴力的构造 (0) xiao1590 2017-03-08 06:27:34