深圳网站建设费用大概,酷炫 网站模板,重庆 网站 建设 公司,营口网站建设第1题 取数问题 查看测评数据信息 有一排N个数#xff0c;你和小明2个人玩游戏#xff0c;每个人轮流从2端取数#xff0c;每次可以从左或右取#xff0c;不能从中间取。你取的所有的数的和是你的得分#xff0c;小明取的所有的数的和是小明的得分。如果你先取#x… 第1题 取数问题 查看测评数据信息 有一排N个数你和小明2个人玩游戏每个人轮流从2端取数每次可以从左或右取不能从中间取。你取的所有的数的和是你的得分小明取的所有的数的和是小明的得分。如果你先取你最多比小明多得多少分 输入格式 第一行一个整数n范围在[0, 100]。 第二行n个整数每个数范围在[1, 10000]。 输出格式 小明足够聪明时你最多多得的分数。 输入/输出例子1 输入 4 3 2 9 1 输出 9 样例解释 第1轮你取3 第2轮他取2 第3轮你取9 第4轮他取1 (39)-(21) 9 样例解释 无 代码 #includebits/stdc.h
using namespace std;
int n,f[105][105],a[105],ans;
int main()
{cinn;for(int i1;in;i)cina[i],f[i][i]a[i];for(int i1;in;i)for(int j1;jin;j)f[j][ji]max(-f[j1][ji]a[j],-f[j][ij-1]a[ij]); coutf[1][n];return 0;
}第1题 数字(number) 查看测评数据信息 有n个数字0到99排成一行每一次可以将相邻的两个数字相加并对100取模即除以100的余数将结果取代之前的两个数一次操作的花费为两个数字相乘。经过n-1次操作后剩下一个数问剩下一个数时总花费的最小值。 输入格式 有若干组数据每组数据第一行为一个正整数nn100表示数字的个数。 第二行为n个正整数0到99 输出格式 每组数据对应的最小花费。 输入/输出例子1 输入 2 18 19 3 40 60 20 输出 342 2400 样例解释 对于第二组数据有两种方案 1、 先将40和60相加得0再将0 和20相加得20总花费为40*600*202400 2、 先将60和20相加得80再将40和80相加得20总花费为60*2040*804400 显然第一种方案较好。 样例解释 无 代码 #includebits/stdc.h
using namespace std;
int n,a[105],f[105][105],d[105];
int main(){while(scanf(%d,n)!EOF){for(int i 0;i 105;i){for(int j 1;j 105;j)f[i][j] 1250000;}for(int i 1;i 105;i){d[i] 0;}for(int i 1;i n;i){cina[i];d[i] d[i-1]a[i];f[i][i] 0;}for(int i 2;i n;i)for(int j i;j n;j){int lt j-i1;for(int k lt;k j;k){int x (d[k]-d[lt-1])%100;int y (d[j]-d[k])%100;f[lt][j]min(f[lt][j],f[lt][k]f[k1][j]x*y);}}coutf[1][n]endl;}return 0;
} 测试 第1题 救灾 查看测评数据信息 为了挽救灾区同胞的生命心系灾区同胞的你准备自己采购一些粮食支援灾区现在假设你一共有资金n元而市场有m种大米每种大米都是袋装产品其价格不等并且只能整袋购买。请问你用有限的资金最多能采购多少公斤粮食呢 输入格式 输入数据首先包含一个正整数C表示有CC10组测试数据每组测试数据的第一行是两个整数n和m(1n100, 1m100),分别表示经费的金额和大米的种类然后是m行数据每行包含3个数ph和c(1p20,1h200,1c20)分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。 输出格式 对于每组测试数据请输出能够购买大米的最多重量你可以假设经费买不光所有的大米并且经费你可以不用完。每个数据的输出占一行。 输入/输出例子1 输入 1 8 2 2 100 4 4 100 2 输出 400 样例解释 无 代码 #include bits/stdc.h
using namespace std;
typedef long long ll;
int a[105],b[105],c[105];
int dp[105];
int n,m;
int main()
{int C;scanf(%d,C);while(C--){memset(dp, 0, sizeof(dp));scanf(%d %d,n,m);for(int i0; im; i){scanf(%d %d %d,a[i],b[i],c[i]);}for(int i0; im; i){for(int j1; jc[i]; j){for(int kn; ka[i]*j; k--){dp[k]max(dp[k-a[i]]b[i], dp[k]);}}}printf(%d\n,dp[n]);}return 0;
} 第3题 光盘 查看测评数据信息 有N张光盘每张光盘有一个价钱现在要从N张光盘中买M张预算为L每张光盘有一个快乐值要求在不超过预算并且恰好买M张使得快乐值总和最大。 输入格式 第一行为一个正整数T1T5表示测试数据个数 每组测试数据第一行为三个正整数NN100,MMN,L(L1000) 接下来的N行每行有两个正整数分别是光盘的价钱与快乐值。 输出格式 每组数据对应的最大快乐值总和保证小于2^31。若无解则输出0. 输入/输出例子1 输入 1 3 2 10 11 100 1 2 9 1 输出 3 样例解释 无 代码 #includeiostream
#includecstdio
#includealgorithm
#includecstring
using namespace std;
const int MAXN 1010;
const int INF 1 31;
struct Movie
{int t,v;
};
Movie movie[MAXN];
int dp[MAXN][MAXN];
int n,m,l;
int main()
{int T;scanf(%d,T);while(T--){scanf(%d%d%d,n,m,l);for(int i 1;i m;i)for(int j 0;j l;j)dp[j][i] -INF;for(int j 0;j l;j)dp[j][0] 0;for(int i 1;i n;i)scanf(%d%d,movie[i].t,movie[i].v);for(int i 1;i n;i)for(int j l;j movie[i].t;j--)for(int k m;k 1;k--)dp[j][k] max(dp[j][k],dp[j-movie[i].t][k-1]movie[i].v);int ans 0;for(int i 1;i l;i)if(dp[i][m] ans)ans dp[i][m];printf(%d\n,ans);}return 0;
} 总结 状态线性DP --?-- 区间DP 阶段长度 阶段的方向2种 ------ 取决于“子问题”
