數(shù)字三角形：用戶登錄
題目描述
上圖給出了一個(gè)數(shù)字三角形。從三角形的頂部到底部有很多條不同的路徑。對(duì)于每條路徑，把路徑上面的數(shù)加起來(lái)可以得到一個(gè)和，你的任務(wù)就是找到最大的和（路徑上的每一步只可沿左斜線向下或右斜線向下走）。
輸入描述
輸入的第一行包含一個(gè)整數(shù)?N?(1≤N≤100)，表示三角形的行數(shù)。
下面的?N?行給出數(shù)字三角形。數(shù)字三角形上的數(shù)都是?0?至?99?之間的整數(shù)。
輸出描述
輸出一個(gè)整數(shù)，表示答案。
輸入輸出樣例
示例
輸入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
輸出
30
運(yùn)行限制
- 最大運(yùn)行時(shí)間：1s
- 最大運(yùn)行內(nèi)存: 128M
代碼：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-429969.html
import java.util.Scanner;
public class 數(shù)字三角形 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();//行數(shù)
int arr[][] = new int[n][n];//初始值
int dp[][] = new int [n][n];//從上到下，加上初始值
for(int i=0;i<n;i++) {
for(int j=0;j<=i;j++) {
arr[i][j] = sc.nextInt();
}
}
dp[0][0] = arr[0][0];
//先給最左邊，賦加上后值
for(int i=1;i<n;i++) {
dp[i][0] = dp[i-1][0]+arr[i][0];
}
//推出每一個(gè)加上，上一個(gè)左右兩側(cè)值之后的最大值
int max=0;
for(int i=1;i<n;i++) {
for(int j=1;j<=i;j++) {
dp[i][j] = arr[i][j] + Math.max(dp[i-1][j-1],dp[i-1][j]);
if(max<dp[i][j])
max = dp[i][j];
}
}
System.out.println(max);
/*
if(n%2!=0) {
System.out.println(dp[n-1][n/2]);
}else {
System.out.println(Math.max(dp[n-1][n/2], dp[n-1][n/2-1]));
}
*/
}
}包子湊數(shù)：用戶登錄
題目描述
小明幾乎每天早晨都會(huì)在一家包子鋪吃早餐。他發(fā)現(xiàn)這家包子鋪有?N?種蒸籠，其中第i?種蒸籠恰好能放?Ai??個(gè)包子。每種蒸籠都有非常多籠，可以認(rèn)為是無(wú)限籠。
每當(dāng)有顧客想買?X?個(gè)包子，賣包子的大叔就會(huì)迅速選出若干籠包子來(lái)，使得這若干籠中恰好一共有?X?個(gè)包子。比如一共有 3 種蒸籠，分別能放 3、4 和 5 個(gè)包子。當(dāng)顧客想買 11 個(gè)包子時(shí)，大叔就會(huì)選 2 籠 3 個(gè)的再加 1 籠 5 個(gè)的（也可能選出 1 籠 3 個(gè)的再加 2 籠 4 個(gè)的）。
當(dāng)然有時(shí)包子大叔無(wú)論如何也湊不出顧客想買的數(shù)量。比如一共有 3 種蒸籠，分別能放 4、5 和 6 個(gè)包子。而顧客想買 7 個(gè)包子時(shí)，大叔就湊不出來(lái)了。
小明想知道一共有多少種數(shù)目是包子大叔湊不出來(lái)的。
輸入描述
第一行包含一個(gè)整數(shù)?N?(1≤N≤100)。
以下 N 行每行包含一個(gè)整數(shù)?Ai??(1≤Ai?≤100)。
輸出描述
一個(gè)整數(shù)代表答案。如果湊不出的數(shù)目有無(wú)限多個(gè)，輸出 INF。
輸入輸出樣例
示例 1
輸入
2
4
5
輸出
6
樣例說(shuō)明
湊不出的數(shù)目包括：1, 2, 3, 6, 7, 11。
示例 2
輸入
2
4
6
輸出
INF
樣例說(shuō)明
所有奇數(shù)都湊不出來(lái)，所以有無(wú)限多個(gè)
運(yùn)行限制
- 最大運(yùn)行時(shí)間：1s
- 最大運(yùn)行內(nèi)存: 256M
代碼：
import java.util.Scanner;
public class 包子湊數(shù) {
static int nums[];
static int n;
static int m = 10000;
static boolean dp[];
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
nums = new int[n + 1];
for (int i = 1; i <= n; i++)
{
nums[i] = sc.nextInt();
}
// 計(jì)算最大公約數(shù)如果不為1則說(shuō)明湊不出的數(shù)有無(wú)數(shù)個(gè)
int gcd = nums[1];
for (int i = 2; i <= n; i++)
{
gcd = gcd(gcd, nums[i]);
}
if(gcd != 1)
{
System.out.println("INF");
return;
}
// 有點(diǎn)向完全背包
// 只要能塞就瘋狂塞
dp = new boolean[m + 10];
// 枚舉每籠
for (int i = 1; i <= n; i++)
{
dp[nums[i]] = true;
// 枚舉出重量
for (int j = 0; j + nums[i] <= m; j++)
{
if(dp[j])
dp[j + nums[i]] = true;
}
}
// 進(jìn)行遍歷找出沒(méi)有被覆蓋的地方
int ans = 0;
for (int i = 1; i <= m; i++)
{
// System.out.println(i);
if(!dp[i]) ans++;
}
System.out.println(ans);
}
public static int gcd(int a,int b)
{
if(b==0) return a;
return gcd(b, a%b);
}
}花開(kāi)花落終有時(shí)，相逢相聚本無(wú)意文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-429969.html
到了這里，關(guān)于數(shù)字三角形+包子湊數(shù)（藍(lán)橋杯JAVA解法）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
