P1796 汤姆斯的天堂梦

汤姆斯的天堂梦

题目描述

汤姆斯生活在一个等级为 $0$ 的星球上。那里的环境极其恶劣每天 $12$ 小时的工作和成堆的垃圾让人忍无可忍。他向往着等级为 $N$ 的星球上天堂般的生活。

有一些航班将人从低等级的星球送上高一级的星球有时需要向驾驶员支付一定金额的费用有时却又可以得到一定的金钱。

汤姆斯预先知道了从 $0$ 等级星球去 $N$ 等级星球所有的航线和需要支付或者可以得到的金钱他想寻找一条价格最低甚至获得金钱最多的航线。

输入格式

第一行一个正整数 $N$$N\le 100$接下来的数据可分为 $N$ 个段落每段的第一行一个整数 $K_i$$K_i\le 100$表示等级为 $i$ 的星球有 $K_i$ 个。

接下来的 $K_i$ 行中第 $j$ 行依次表示与等级为 $i$编号为 $j$ 的星球相连的等级为 $i-1$ 的星球的编号和此航线需要的费用正数表示支出负数表示收益费用的绝对值不超过 $1000$。

每行以 $0$ 结束每行的航线数 $\le 100$。

输出格式

输出所需或所得费用。正数表示支出负数表示收益。

样例 #1

样例输入 #1

3
2
1 15 0
1 5 0
3
1 -5 2 10 0
1 3 0
2 40 0
2
1 1 2 5 3 -5 0
2 -19 3 -20 0

样例输出 #1

-1

提示

对于 $100\%$ 的数据$1\le N\le 100$$1\le K_i\le 100$。

样例解释

思路

动态规划以i为等级j为编号L表示第i级编号j的星球到第i-1级编号k动态规划方程f[i,j]=min{f[i-1,j]+L}

代码

#include<bits/stdc++.h>
using namespace std;
int n,a,b,c,f[2000][2000];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a;
		for(int j=1;j<=a;j++) 
		{
			f[i][j]=0x7ffffff;
			cin>>b; 
			while (b!=0) 
			{
				cin>>c;
				f[i][j]=min(f[i-1][b]+c,f[i][j]);
				cin>>b;
			}
		}
	}
	int minn=0x7ffffff;
	for (int i=1;i<=a;i++)
	  minn=min(f[n][i],minn);
	cout<<minn<<endl;
	return 0;
}

P1806 跑步

跑步

题目描述

路人甲准备跑 $n$ 圈来锻炼自己的身体他准备分多次$>1$跑完每次都跑正整数圈然后休息下再继续跑。

为了有效地提高自己的体能他决定每次跑的圈数都必须比上次跑的多。

可以假设他刚开始跑了 $0$ 圈那么请问他可以有多少种跑完这 $n$ 圈的方案

输入格式

一行一个整数代表 $n$。

输出格式

一个整数表示跑完这 $n$ 圈的方案数。

样例 #1

样例输入 #1

212

样例输出 #1

995645335

提示

数据规模与约定

对于 $100\%$ 的数据保证 $5\le n\le 500$。

思路

动态规划数组的第i个下标表示前i圈的方案总数

代码

#include<bits/stdc++.h>
using namespace std;
long long n,ans[501]; 
int main()
{
    scanf("%d",&n);
    ans[0]=1;
    for (int i=1;i<=n;i++)
		for (int j=n;j>=i;j--) 
		    ans[j]+=ans[j-i];
	cout<<ans[n]-1<<endl;
    return 0;
}

P8742 [蓝桥杯 2021 省 AB] 砝码称重

[蓝桥杯 2021 省 AB] 砝码称重

题目描述

你有一架天平和 $N$ 个砝码, 这 $N$ 个砝码重量依次是 $W_1,W_2,\cdots ,W_N$ 。 请你计算一共可以称出多少种不同的重量?

注意砝码可以放在天平两边。

输入格式

输入的第一行包含一个整数 $N$ 。

第二行包含 $N$ 个整数: $W_1,W_2,W_3,\cdots ,W_N$ 。

输出格式

输出一个整数代表答案。

样例 #1

样例输入 #1

3
1 4 6

样例输出 #1

10

提示

【样例说明】

能称出的 10 种重量是: $1、2、3、4、5、6、7、9、10、11$ 。

$$\begin{array}{rl}& 1=1\\ & 2=6-4(\text{ 天平一边放 }6,\text{ 另一边放 4) }\\ & 3=4-1\\ & 4=4\\ & 5=6-1\\ & 6=6\\ & 7=1+6\\ & 9=4+6-1\\ & 10=4+6\\ & 11=1+4+6\end{array}$$

【评测用例规模与约定】

对于 $50\%$ 的评测用例, $1\le N\le 15$ 。

对于所有评测用例, $1\le N\le 100,N$ 个砝码总重不超过 $10^5$。

蓝桥杯 2021 第一轮省赛 A 组 F 题B 组 G 题。

思路

动态规划