广州网站建设V芯ee8888e,张家港seo建站,生态农业网站模板,常用于网站推广的营销手段是题干#xff1a;
问题描述 给n个有序整数对ai bi#xff0c;你需要选择一些整数对 使得所有你选定的数的aibi的和最大。并且要求你选定的数对的ai之和非负#xff0c;bi之和非负。
输入格式 输入的第一行为n#xff0c;数对的个数 以下n行每行两个整数 ai bi
输出格…题干
问题描述 给n个有序整数对ai bi你需要选择一些整数对 使得所有你选定的数的aibi的和最大。并且要求你选定的数对的ai之和非负bi之和非负。
输入格式 输入的第一行为n数对的个数 以下n行每行两个整数 ai bi
输出格式 输出你选定的数对的aibi之和
样例输入
5 -403 -625 -847 901 -624 -708 -293 413 886 709
样例输出
1715
数据规模和约定 1n100 -1000ai,bi1000
时间限制1.0s 内存限制256.0MB
解题报告
不直接计算选定的数的aibi的和而是转化为计算在ai的和一定的情况下尽量使选定的bi的和最大。于是变成为一个01背包问题ai的值作为物体的重量bi的值作为该物体的价值。首先过滤掉所有ai和bi均小于0的数对令dp[i][j]表示前i个数对选定的ai的和为j的情况下bi的和的最大值将dp[i][j]初始化为-INF再将所有已知合法情况初始化dp[i][a[i]] b[i]之后dp[i][j] max(dp[i - 1][j], dp[i][j])若j - a[i]存在dp[i][j] max(dp[i][j], dp[i - 1][j - a[i]] b[i])。最后再统一加偏移量ZERO。值得注意的是这个背包问题虽然也可以优化成一维但是没必要如果优化成一维对于这题代码不会更简练反而会复杂不少因为这题初始化的时候不能只对二维数组的第一行进行初始化需要每一行都有一个值进行初始化所以最好的办法就是直接开二维数组做最朴素的01背包而且这题空间给的足够大所以不需要担心MLE的问题。
AC代码空间大概78MB
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
int tot;
int a[101],b[101];
int dp[101][200000 5];//截止到第i个a[i]和为j的情况下b[i] 的最大值
int zero 100000;
const int INF 0x3f3f3f3f;
int main()
{int n;cinn;for(int x,y,i 1; in; i) {scanf(%d%d,x,y);if(x 0 y 0) continue;a[tot] x, b[tot] y;} for(int i 0; itot; i) {for(int j -100000; j100000; j) {dp[i][j zero] -INF;}}for(int i 1; itot; i) {dp[i][a[i] zero] b[i];}for(int i 2; itot; i) {for(int j -100000; j100000; j) {if(dp[i-1][j zero] ! -INF) dp[i][j zero] max(dp[i][jzero],dp[i-1][j zero]);if(j - a[i] zero 0 j - a[i] zero 200000) //这句必须加。 dp[i][j zero] max(dp[i][j zero] , dp[i-1][j-a[i] zero] b[i]);}}int ans 0;for(int j 100000; j0; j--) {if(dp[tot][j zero] 0) ans max(ans, dp[tot][j zero] j);}printf(%d\n,ans);return 0 ;}
或者这样也可以过空间162.9MB
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e5 5;
int tot;
int a[MAX],b[MAX];
int dp[105][400000 5];//截止到第i个a[i]和为j的情况下b[i] 的最大值
int zero 100000;
const int INF 0x3f3f3f3f;
int main()
{int n;cinn;for(int x,y,i 1; in; i) {scanf(%d%d,x,y);if(x 0 y 0) continue;a[tot] x, b[tot] y;} for(int i 0; itot; i) {for(int j -100000; j300000; j) {//这里变了dp[i][j zero] -INF;}}for(int i 1; itot; i) {dp[i][a[i] zero] b[i];}for(int i 2; itot; i) {for(int j -100000; j100000; j) {if(dp[i-1][j zero] ! -INF) dp[i][j zero] max(dp[i][jzero],dp[i-1][j zero]);if(j - a[i] zero 0 )//这里变了dp[i][j zero] max(dp[i][j zero] , dp[i-1][j-a[i] zero] b[i]);}}int ans 0;for(int j 100000; j0; j--) {if(dp[tot][j zero] 0) ans max(ans, dp[tot][j zero] j);}printf(%d\n,ans);return 0 ;}
或者这样
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e5 5;
int tot;
int a[MAX],b[MAX];
int dp[105][400000 5];//截止到第i个a[i]和为j的情况下b[i] 的最大值
int zero 100000;
const int INF 0x3f3f3f3f;
int main()
{int n;cinn;for(int x,y,i 1; in; i) {scanf(%d%d,x,y);if(x 0 y 0) continue;a[tot] x, b[tot] y;} for(int i 0; itot; i) {for(int j -100000; j300000; j) {dp[i][j zero] -INF;}}dp[0][zero] 0;
// for(int i 1; itot; i) {
// dp[i][a[i] zero] b[i];
// }for(int i 1; itot; i) {for(int j -100000; j100000; j) {if(dp[i-1][j zero] ! -INF) dp[i][j zero] max(dp[i][jzero],dp[i-1][j zero]);if(j - a[i] zero 0 )dp[i][j zero] max(dp[i][j zero] , dp[i-1][j-a[i] zero] b[i]);}}int ans 0;for(int j 100000; j0; j--) {if(dp[tot][j zero] 0) ans max(ans, dp[tot][j zero] j);}printf(%d\n,ans);return 0 ;}
当然如果你连if(j - a[i] zero 0 )也不想写那就可以直接ZERO设为200000就行了。
总结 首先需要知道他和0-1背包还是有区别的因为0-1背包是可以不初始化成-INF的但是那样表示的是可以表示的最大价值因为价值都是正数所以0可以当成是非法状态。而这个题必须初始化成-INF因为这题所谓的“价值”可以是负数我们需要新设置一个非法状态并且把唯一一个合法状态设置好dp[0][zero]0;来方便后面的转移。其实这样说来就可以改成一维的0-1背包了。
错误代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e5 5;
int tot;
int a[MAX],b[MAX];
int dp[400000 5];//截止到第i个a[i]和为j的情况下b[i] 的最大值
int zero 100000;
const int INF 0x3f3f3f3f;
int main()
{int n;cinn;for(int x,y,i 1; in; i) {scanf(%d%d,x,y);if(x 0 y 0) continue;a[tot] x, b[tot] y;} for(int j -100000; j300000; j) {dp[j zero] -INF;}dp[zero] 0;for(int i 1; itot; i) {for(int j 100000; j-100000; j--) {if(j - a[i] zero 0) dp[j zero] max(dp[j zero] , dp[j-a[i] zero] b[i]);}}int ans 0;for(int j 100000; j0; j--) {if(dp[j zero] 0) ans max(ans, dp[j zero] j);}printf(%d\n,ans);return 0 ;}
但是仔细一想这样是错误的因为就地滚动的前提是后面的数只能用到前面的数而你这个题a[i]有正有负所以可能用到前面的状态也可能用到后面的状态所以不能优化成一维。
