花了幾天時間才做完一套試題，挺慢抽碌，不過收獲不小悍赢，寫一下自己的解題思路。試題鏈接
雙核處理
一種雙核CPU的兩個核能夠同時的處理任務货徙，現(xiàn)在有n個已知數(shù)據(jù)量的任務需要交給CPU處理左权，假設已知CPU的每個核1秒可以處理1kb，每個核同時只能處理一項任務痴颊。n個任務可以按照任意順序放入CPU進行處理赏迟，現(xiàn)在需要設計一個方案讓CPU處理完這批任務所需的時間最少，求這個最小的時間蠢棱。
輸入描述:
輸入包括兩行：
第一行為整數(shù)n(1 ≤ n ≤ 50)
第二行為n個整數(shù)length[i](1024 ≤ length[i] ≤ 4194304)锌杀，表示每個任務的長度為length[i]kb甩栈，每個數(shù)均為1024的倍數(shù)。
輸出描述:
輸出一個整數(shù)糕再，表示最少需要處理的時間
輸入例子1:
5
3072 3072 7168 3072 1024
輸出例子1:
9216
解題思路
一個cpu處理n1個任務所用時間為t1量没，當t1最接近(sum/2)時，
此時t2也最接近(sum/2)突想，完成任務所需最小時間就是t1殴蹄、t2中的最小值。
也就是說只要求出一個cpu所處理任務即可猾担。
現(xiàn)在的目標是：在(sum/2)時間內(nèi)袭灯，能完成的最多任務。也就是背包問題了
public class MultiKernel {
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
int []arr=new int[n];
int sum=0;
for(int i=0;i<n;i++) {
arr[i] = scanner.nextInt()>>9;
sum+=arr[i];
}
//先排序
Arrays.sort(arr);
System.out.print(concurent2(arr,sum)<<9);
}
/*
dep[i]表示時間為i時能完成的最多任務重量(時間)绑嘹。
dep[j]=max(dep[j],dep[j-t[i]]+t[i])表示找出選擇第i個任務和不選第i個任務時的最大值稽荧。
*/
public static int concurent2(int[] arr,int sum){
//java語言特性，全為0
int []dep=new int[sum/2+1];
dep[0]=0;
int n=arr.length;
int i,j;
for(i=0;i<n;i++){
for(j=sum/2;j>=arr[i];j--){
dep[j]=Math.max(dep[j],dep[j-arr[i]]+arr[i]);
}
}
//找出兩個cpu中所用時間最長的圾叼。這就是最長時間000
return Math.max(sum-dep[sum/2],dep[sum/2]);
}
}
結果
趕去公司
終于到周末啦蛤克！小易走在市區(qū)的街道上準備找朋友聚會，突然服務器發(fā)來警報,小易需要立即回公司修復這個緊急bug夷蚊。假設市區(qū)是一個無限大的區(qū)域构挤，每條街道假設坐標是(X，Y)惕鼓，小易當前在(0筋现，0)街道，辦公室在(gx,gy)街道上箱歧。小易周圍有多個出租車打車點矾飞，小易趕去辦公室有兩種選擇，一種就是走路去公司呀邢，另外一種就是走到一個出租車打車點洒沦，然后從打車點的位置坐出租車去公司。每次移動到相鄰的街道(橫向或者縱向)走路將會花費walkTime時間价淌，打車將花費taxiTime時間申眼。小易需要盡快趕到公司去，現(xiàn)在小易想知道他最快需要花費多少時間去公司蝉衣。
輸入描述:
輸入數(shù)據(jù)包括五行:
第一行為周圍出租車打車點的個數(shù)n(1 ≤ n ≤ 50)
第二行為每個出租車打車點的橫坐標tX[i] (-10000 ≤ tX[i] ≤ 10000)
第三行為每個出租車打車點的縱坐標tY[i] (-10000 ≤ tY[i] ≤ 10000)
第四行為辦公室坐標gx,gy(-10000 ≤ gx,gy ≤ 10000),以空格分隔
第五行為走路時間walkTime(1 ≤ walkTime ≤ 1000)和taxiTime(1 ≤ taxiTime ≤ 1000),以空格分隔
輸出描述:
輸出一個整數(shù)表示括尸，小易最快能趕到辦公室的時間
輸入例子1:
2
-2 -2
0 -2
-4 -2
15 3
輸出例子1:
42
解題思路
這道題初看時是一道關于圖的回溯問題，但是看一下數(shù)值范圍就會發(fā)現(xiàn)如果是回溯的話肯定會超時病毡。再仔細閱讀發(fā)現(xiàn)這題很簡單濒翻。
(X1,Y1)和(X2,Y2)的最短距離就是abs(X1-X2)+abs(Y1-Y2)
找出完全步行的最短時間再和先到停車點再到公司的最短時間比較，找到最小的即可
public class GotoCompany {
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
int x[]=new int[n];
int y[]=new int[n];
int gX,gY,walkTime,taxiTime;
int i,j;
for(i=0;i<n;i++){
x[i]=scanner.nextInt();
}
for(i=0;i<n;i++){
y[i]=scanner.nextInt();
}
gX=scanner.nextInt();
gY=scanner.nextInt();
walkTime=scanner.nextInt();
taxiTime=scanner.nextInt();
//完全步行所用時間
int minTime=(Math.abs(gX)+Math.abs(gY))*walkTime;
int curTime;
for(i=0;i<n;i++){
curTime=0;
//走到停車點所用時間
curTime+=walkTime*(Math.abs(x[i])+Math.abs(y[i]));
//加上從停車點到公司時間
curTime+=taxiTime*(Math.abs(gX-x[i])+Math.abs(gY-y[i]));
//比較
minTime=curTime<minTime?curTime:minTime;
}
System.out.print(minTime);
}
}
結果
調整隊形
在幼兒園有n個小朋友排列為一個隊伍，從左到右一個挨著一個編號為(0~n-1)有送。其中有一些是男生淌喻，有一些是女生，男生用'B'表示娶眷，女生用'G'表示似嗤。小朋友們都很頑皮，當一個男生挨著的是女生的時候就會發(fā)生矛盾届宠。作為幼兒園的老師，你需要讓男生挨著女生或者女生挨著男生的情況最少乘粒。你只能在原隊形上進行調整豌注，每次調整只能讓相鄰的兩個小朋友交換位置，現(xiàn)在需要盡快完成隊伍調整灯萍，你需要計算出最少需要調整多少次可以讓上述情況最少轧铁。例如：
GGBBG -> GGBGB -> GGGBB
這樣就使之前的兩處男女相鄰變?yōu)橐惶幭噜彛枰{整隊形2次
輸入描述:
輸入數(shù)據(jù)包括一個長度為n且只包含G和B的字符串.n不超過50.
輸出描述:
輸出一個整數(shù)旦棉，表示最少需要的調整隊伍的次數(shù)
輸入例子1:
GGBBG
輸出例子1:
2
解題思路
目的就是進行劃分,從某一點開始左側全為'G'(或'B'),右側全為'B'(或'G').
在這里一個重要的規(guī)律是:將兩個數(shù)arr[i] arrj交換,需要的交換次數(shù)是(j-i+1).
那么類似于快速排序中的hoare劃分,循環(huán)將最左側的'G'(或'B')與最右側的'B'(或'G')交換,直到相交.這樣就能得到一個劃分.
取決于'G'和'B'的數(shù)目和位置,可能存在兩種:1齿风、'G'在左側 2、'G'在右側
為了方便我嘗試分別將'G'放在左側和右側绑洛，再比較兩者中交換次數(shù)較小者救斑。
import java.util.Arrays;
import java.util.Scanner;
public class AdjustArray {
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
char[] arr= scanner.nextLine().toCharArray();
int n=arr.length;
int i,j;
int min=Integer.MAX_VALUE;
int curMin;
i=-1;
j=n;
curMin=0;
//復制數(shù)組
char[]temp= Arrays.copyOf(arr,arr.length);
//左側全為'B'
while(i<j){
while(i<n-1&&temp[++i]=='G');
while(j>0&&temp[--j]=='B');
if(i<j) {
swap(temp, i, j);
curMin += (j - i);
}
}
min=curMin<min?curMin:min;
curMin=0;
i=-1;
j=n;
//左側全為'G'
while(i<j){
while(i<n-1&&arr[++i]=='B');
while(j>0&&arr[--j]=='G');
if(i<j) {
swap(arr,i,j);
curMin += (j - i);
}
}
//比較找出最小值
min=curMin<min?curMin:min;
System.out.print(min);
}
public static void swap(char[] arr,int i,int j){
char temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
結果
消除重復元素
小易有一個長度為n序列，小易想移除掉里面的重復元素真屯，但是小易想是對于每種元素保留最后出現(xiàn)的那個脸候。小易遇到了困難,希望你來幫助他。
輸入描述:
輸入包括兩行：
第一行為序列長度n(1 ≤ n ≤ 50)
第二行為n個數(shù)sequence[i](1 ≤ sequence[i] ≤ 1000)绑蔫，以空格分隔
輸出描述:
輸出消除重復元素之后的序列运沦，以空格分隔，行末無空格
輸入例子1:
9
100 100 100 99 99 99 100 100 100
輸出例子1:
99 100
解題思路
很簡單配深，從后向前携添，使用set過濾，最后輸出時也是從后向前篓叶。
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Q4 {
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
int []arr=new int[n];
int i,j;
for(i=0;i<n;i++){
arr[i]=scanner.nextInt();
}
Set<Integer> set=new HashSet<>();
int []res=new int[n];
j=0;
for(i=n-1;i>=0;i--){
if(!set.contains(arr[i])){
set.add(arr[i]);
res[j++]=arr[i];
}
}
for(j-=1;j>=0;j--){
System.out.print(res[j]);
if(j!=0)
System.out.print(" ");
}
}
}
結果
魔力手環(huán)
小易擁有一個擁有魔力的手環(huán)上面有n個數(shù)字(構成一個環(huán)),當這個魔力手環(huán)每次使用魔力的時候就會發(fā)生一種奇特的變化：每個數(shù)字會變成自己跟后面一個數(shù)字的和(最后一個數(shù)字的后面一個數(shù)字是第一個),一旦某個位置的數(shù)字大于等于100就馬上對100取模(比如某個位置變?yōu)?03,就會自動變?yōu)?).現(xiàn)在給出這個魔力手環(huán)的構成烈掠，請你計算出使用k次魔力之后魔力手環(huán)的狀態(tài)。
輸入描述:
輸入數(shù)據(jù)包括兩行：
第一行為兩個整數(shù)n(2 ≤ n ≤ 50)和k(1 ≤ k ≤ 2000000000),以空格分隔
第二行為魔力手環(huán)初始的n個數(shù)澜共，以空格分隔向叉。范圍都在0至99.
輸出描述:
輸出魔力手環(huán)使用k次之后的狀態(tài)，以空格分隔嗦董，行末無空格母谎。
輸入例子1:
3 2
1 2 3
輸出例子1:
8 9 7
解題思路
看到這道題首先想到的時循環(huán)x次后會回到初始狀態(tài)，更巧的是我測試用70京革、80奇唤、90帶入結果符合我的設想（只能說自己用來測試的數(shù)據(jù)太巧了）幸斥，最后看了別人的解答才知道要用矩陣快速乘來計算。
以A={{1},{2},{3}}這個3行1列的矩陣為例咬扇，B={{1,0,1},{1,1,0},{0,1,1}}(這個矩陣要從列來看)對它進行一次操作相當于
A*B
要對A進行k次操作相當于
A*B^k
最后結合霍納法則對B^k的計算進行簡化
import java.util.Scanner;
public class MagicBand {
//使用矩陣快速乘思想
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
int k=scanner.nextInt();
int[][]arr=new int[1][n];
for(int i=0;i<n;i++)
arr[0][i]=scanner.nextInt();
//初始化系數(shù)矩陣甲葬，要從列看
int [][]mul=new int[n][n];
for(int i=0;i<n;i++){
mul[i][i]=1;
if(i<n-1){
mul[i+1][i]=1;
}else{
mul[0][i]=1;
}
}
//根據(jù)霍納法則簡化
while(k>0){
if(k%2==1)
arr=multi(arr,mul);
mul=multi(mul,mul);
k>>=1;
}
for(int i=0;i<n;i++){
System.out.print(arr[0][i]);
if(i!=n-1)
System.out.print(" ");
}
}
//矩陣相乘，通用版本
public static int[][] multi(int[][]a,int[][]b){
int row=a.length;
int n=a[0].length;
int col=b[0].length;
int [][]c=new int[row][col];
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
c[i][j]=0;
for(int k=0;k<n;k++){
//優(yōu)化懈贺，可以節(jié)省一次乘法
if(a[i][k]==0||b[k][j]==0)
continue;
c[i][j]+=a[i][k]*b[k][j];
//注意不能超過100
if(c[i][j]>=100)
c[i][j]%=100;
}
}
}
return c;
}
/*
!!!!!!
下面是我使用自己的循環(huán)x次后會回到初始狀態(tài)的思想做的经窖，是錯的，而且效率很低梭灿，引以為戒
*/
public static void resolve(int[]arr,int k,int[]origin){
final int n=arr.length;
int i,j;
int head=0;
boolean flag=true;
for(i=0;i<k;i++){
for(j=0;j<n;j++){
if(j==0){
head=(arr[0]+arr[1])%100;
}else{
arr[j]=(arr[j]+arr[(j+1)%n])%100;
}
}
if(head>1000000){
for(int p=0;p<n;p++)
arr[p]%=100;
}
arr[0]=head;
if(flag&&circle(origin,arr)){
k-=(i+1);
k%=(i+1)*n;
//注意這里結束后在外層循環(huán)i會自增所以需要再減去1
i=-1;
flag=false;
}
}
}
public static boolean circle(int[]origin,int[]copyofArr){
final int n=origin.length;
for(int i=0;i<n;i++){
if(i!=n-1){
if(origin[i]!=copyofArr[i+1])
return false;
}else{
if(origin[n-1]!=copyofArr[0])
return false;
}
}
return true;
}
}
結果
工作安排
現(xiàn)在有n位工程師和6項工作(編號為0至5)画侣，現(xiàn)在給出每個人能夠勝任的工作序號表(用一個字符串表示，比如：045堡妒，表示某位工程師能夠勝任0號配乱，4號，5號工作)∑こ伲現(xiàn)在需要進行工作安排搬泥，每位工程師只能被安排到自己能夠勝任的工作當中去，兩位工程師不能安排到同一項工作當中去伏尼。如果兩種工作安排中有一個人被安排在的工作序號不一樣就被視為不同的工作安排忿檩，現(xiàn)在需要計算出有多少種不同工作安排計劃。
輸入描述:
輸入數(shù)據(jù)有n+1行：
第一行為工程師人數(shù)n(1 ≤ n ≤ 6)
接下來的n行烦粒，每行一個字符串表示第i(1 ≤ i ≤ n)個人能夠勝任的工作(字符串不一定等長的)
輸出描述:
輸出一個整數(shù)休溶，表示有多少種不同的工作安排方案
輸入例子1:
6
012345
012345
012345
012345
012345
012345
輸出例子1:
720
解題思路
先理解下面：
- 每個工程師有且只有一項工作
- 不必所有工作都需要被做
很不幸最初我理解的是，所有工作必須被做扰她，每個工程師可以有任意項工作兽掰。。
這道題很適合用回溯法解決徒役。(仍然是看過解析才懂)
import java.util.*;
public class WorkArrangement {
//只要每個工程師有事做就行孽尽，不必每項任務都有人做
static int count=0;
Set<Integer> s = new HashSet<>(Arrays.asList(0,1,2,3,4,5));
static final int N=6;
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
//第i個工程師能做第j件工作
char [][]worker=new char[n][];
scanner.nextLine();
for(int i=0;i<n;i++){
worker[i]=scanner.nextLine().toCharArray();
}
backreverse(worker,0,new HashSet<Character>());
System.out.print(count);
}
public static void backreverse(char[][] worker,int index,HashSet<Character> set){
//如果已經(jīng)全部安排，說明成功
if(index>=worker.length){
count++;
return;
}
char[] work=worker[index];
for(int i=0;i<work.length;i++){
if(!set.contains(work[i])){
//把這項工作記錄下來說明已分配
set.add(work[i]);
//為下一位工程師分配
backreverse(worker,index+1,set);
//移除忧勿，為這個工程師分配下一個任務的情況
set.remove(work[i]);
}
}
}
}
結果
集合
小易最近在數(shù)學課上學習到了集合的概念,集合有三個特征：1.確定性 2.互異性 3.無序性.
小易的老師給了小易這樣一個集合：
S = { p/q | w ≤ p ≤ x, y ≤ q ≤ z }
需要根據(jù)給定的w杉女，x，y鸳吸，z,求出集合中一共有多少個元素熏挎。小易才學習了集合還解決不了這個復雜的問題,需要你來幫助他。
輸入描述:
輸入包括一行：
一共4個整數(shù)分別是w(1 ≤ w ≤ x)晌砾，x(1 ≤ x ≤ 100)坎拐，y(1 ≤ y ≤ z)，z(1 ≤ z ≤ 100).以空格分隔
輸出描述:
輸出集合中元素的個數(shù)
輸入例子1:
1 10 1 1
輸出例子1:
10
解題思路
唯一要注意的是它沒有限定結果是整數(shù)，所以要以double型存儲和計算
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class CollectionNumber {
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
int w,x,y,z;
w=scanner.nextInt();
x=scanner.nextInt();
y=scanner.nextInt();
z=scanner.nextInt();
Set<Double> set=new HashSet<>();
for(int i=w;i<=x;i++){
for(int j=y;j<=z;j++){
double temp=i/(double)j;
set.add(temp);
}
}
System.out.print(set.size());
}
}
結果
奇怪的表達式求值
常規(guī)的表達式求值哼勇，我們都會根據(jù)計算的優(yōu)先級來計算都伪。比如*/的優(yōu)先級就高于+-。但是小易所生活的世界的表達式規(guī)則很簡單积担，從左往右依次計算即可陨晶，而且小易所在的世界沒有除法，意味著表達式中沒有/帝璧，只有(+, - 和 *)∪焖觯現(xiàn)在給出一個表達式称龙，需要你幫忙計算出小易所在的世界這個表達式的值為多少
輸入描述:
輸入為一行字符串克伊，即一個表達式皮官。其中運算符只有-,+,*。參與計算的數(shù)字只有0~9.
保證表達式都是合法的撮躁，排列規(guī)則如樣例所示。
輸出描述:
輸出一個數(shù)买雾，即表達式的值
輸入例子1:
3+5*7
輸出例子1:
56
解題思路
同樣很簡單把曼，直接看代碼
public class Calculate {
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
char[] arr=scanner.nextLine().toCharArray();
int i=0;
Set<Character> operator=new HashSet<>(Arrays.asList('0','1','2','3','4','5','6','7','8','9'));
int left=0;
char oper;
int right;
while(operator.contains(arr[i])){
left+=left*10+(arr[i]-'0');
i++;
}
while(i<arr.length){
right=0;
oper=arr[i++];
while(i<arr.length&&operator.contains(arr[i])){
right+=right*10+(arr[i]-'0');
i++;
}
left=cal(left,oper,right);
}
System.out.print(left);
}
public static int cal(int left,char oper,int right){
int result=0;
switch (oper){
case '+':
result=left+right;
break;
case '-':
result=left-right;
break;
case '*':
result=left*right;
break;
}
return result;
}
}
涂棋盤
小易有一塊n*n的棋盤，棋盤的每一個格子都為黑色或者白色漓穿，小易現(xiàn)在要用他喜歡的紅色去涂畫棋盤嗤军。小易會找出棋盤中某一列中擁有相同顏色的最大的區(qū)域去涂畫，幫助小易算算他會涂畫多少個棋格晃危。
輸入描述:
輸入數(shù)據(jù)包括n+1行：
第一行為一個整數(shù)n(1 ≤ n ≤ 50),即棋盤的大小
接下來的n行每行一個字符串表示第i行棋盤的顏色叙赚，'W'表示白色，'B'表示黑色
輸出描述:
輸出小易會涂畫的區(qū)域大小
輸入例子1:
3
BWW
BBB
BWB
輸出例子1:
3
解題思路
對每一列進行計算僚饭，找出最長的震叮。
public class MaxArea {
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
scanner.nextLine();
boolean[][] table=new boolean[n][n];
int i,j;
//白1黑0
for(i=0;i<n;i++){
char []arr=scanner.nextLine().toCharArray();
for(j=0;j<n;j++){
if(arr[j]=='B'){
table[i][j]=false;
}else{
table[i][j]=true;
}
}
}
int max=0;
boolean flag;
int curMax;
for(j=0;j<n;j++){
flag=table[0][j];
curMax=1;
for(i=1;i<n;i++){
if(table[i][j]==flag){
curMax++;
}else{
curMax=1;
flag=!flag;
}
max=(curMax>max)?curMax:max;
}
}
System.out.print(max);
}
}
結果
小易記單詞
小易參與了一個記單詞的小游戲。游戲開始系統(tǒng)提供了m個不同的單詞鳍鸵，小易記憶一段時間之后需要在紙上寫出他記住的單詞苇瓣。小易一共寫出了n個他能記住的單詞，如果小易寫出的單詞是在系統(tǒng)提供的偿乖，將獲得這個單詞長度的平方的分數(shù)击罪。注意小易寫出的單詞可能重復，但是對于每個正確的單詞只能計分一次贪薪。
輸入描述:
輸入數(shù)據(jù)包括三行：
第一行為兩個整數(shù)n(1 ≤ n ≤ 50)和m(1 ≤ m ≤ 50)媳禁。以空格分隔
第二行為n個字符串，表示小易能記住的單詞画切，以空格分隔竣稽，每個單詞的長度小于等于50。
第三行為m個字符串，系統(tǒng)提供的單詞丧枪，以空格分隔光涂，每個單詞的長度小于等于50。
輸出描述:
輸出一個整數(shù)表示小易能獲得的分數(shù)
輸入例子1:
3 4
apple orange strawberry
strawberry orange grapefruit watermelon
輸出例子1:
136
解題思路
只要對小易的輸入進行過濾就行了
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
//注意數(shù)據(jù)的讀取
public class RememberVocaly {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n=scanner.nextInt();
int m=scanner.nextInt();
ArrayList<String> sysArr=new ArrayList<>();
ArrayList<String> yiArr=new ArrayList<>();
int i=0,j=0;
while(scanner.hasNext()){
String s=scanner.next();
//對小易的輸入要進行過濾
if(i<n){
if(!yiArr.contains(s)){
yiArr.add(s);
}
i++;
}else{
sysArr.add(s);
j++;
if(j==m)
break;
}
}
scanner.close();
int score=0;
for(i=0;i<yiArr.size();i++){
String sa=yiArr.get(i);
if(sysArr.contains(sa)){
int len=sa.length();
score+=len*len;
}
}
System.out.print(score);
}
}
結果
堆磚塊
小易有n塊磚塊拧烦，每一塊磚塊有一個高度忘闻。小易希望利用這些磚塊堆砌兩座相同高度的塔。為了讓問題簡單恋博，磚塊堆砌就是簡單的高度相加齐佳，某一塊磚只能使用在一座塔中一次。小易現(xiàn)在讓能夠堆砌出來的兩座塔的高度盡量高债沮，小易能否完成呢炼吴。
輸入描述:
輸入包括兩行：
第一行為整數(shù)n(1 ≤ n ≤ 50)，即一共有n塊磚塊
第二行為n個整數(shù)疫衩，表示每一塊磚塊的高度height[i] (1 ≤ height[i] ≤ 500000)
輸出描述:
如果小易能堆砌出兩座高度相同的塔硅蹦，輸出最高能拼湊的高度，如果不能則輸出-1.
保證答案不大于500000闷煤。
輸入例子1:
3
2 3 5
輸出例子1:
5
解題思路
這題和雙核處理那道題挺像的童芹，當時這里并不需要用到所有的磚塊，自己嘗試了依次減去磚塊并用剩余磚塊進行背包處理鲤拿，只能通過90%假褪。最終又看了解析(哭)。
它是用動態(tài)規(guī)劃解決的＝辍生音！
dp[i][j]表示用前i個磚塊，高低塔高度差為j時窒升，低塔的高度
dp[i][j]為以下中的最大值
1缀遍、dp[i-1][j+weigh[i]]+weigh[i] 第i塊磚塊放在低塔后低塔高度仍然低于高塔。
2异剥、dp[i-1][high-j]+high-j 第i塊磚塊放在低塔后低塔高度高于高塔
3瑟由、dp[i-1][j-weigh[i]] 第i塊磚塊放在高塔
4、dp[i][j] 不放
可以看出只用到了dp[i]和dp[i-1],因此可以用=兩個數(shù)組代替二位數(shù)組減少內(nèi)存
2示意
public class Q11 {
static int sum;
static int[] height;
public static void main(String[]args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
height = new int[n];
sum = 0;
for (int i = 0; i < n; i++) {
height[i] = scanner.nextInt();
sum += height[i];
}
Arrays.sort(height);
int []dp=new int[sum +1];
Arrays.fill(dp,Integer.MIN_VALUE);
dp[0]=0;
for(int i=1;i<=n;i++){
int []temp=new int[sum+1];
int high=height[i-1];
Arrays.fill(temp,Integer.MIN_VALUE);
for(int j=0;j<=sum;j++){
//根據(jù)j冤寿、high的大小差距可以過濾一種情況
//向高塔放
if(j>high){
temp[j]=Math.max(temp[j],dp[j-high]);
}
if(j<=high){//向低塔放歹苦，放后低塔變高塔
temp[j]= Math.max(temp[j],dp[high-j]+high-j);
}
//向低塔放，放后低塔仍舊是低塔
if(j+high<=sum){
temp[j]=Math.max(temp[j],dp[j+high]+high);
}
//不放
temp[j]=Math.max(temp[j],dp[j]);
}
dp=temp;
}
if(dp[0]>0){
System.out.print(dp[0]);
}else{
System.out.print(-1);
}
}
//自己的方法督怜，超時
/* public static int tryBuild(int[]arr,int sum){
//使用數(shù)組的子序列構建
int max=-1;
if(arr.length>1) {
int[][] arrs=new int[arr.length][arr.length-1];
for (int i = 0; i < arr.length; i++) {
int m=0;
for(int j=0;j<arrs[i].length;j++,m++){
if(j==i)
m++;
arrs[i][j]=arr[m];
}
max = findMax(sum - arr[i],arrs[i] );
if (max != -1) {
return max;
}
}
//子數(shù)組的新一輪循環(huán)
for(int i=0;i<arr.length;i++){
int diff=sum-arr[i];
if(diff> Q11.sum /2)
max=tryBuild(arrs[i],sum-arr[i]);
if(max!=-1)
return max;
}
}
return -1;
}
public static int findMax(int sum,int[]arr){
int max=-1;
if(sum%2!=0)
return max;
int[] dep = new int[sum / 2 + 1];
dep[0] = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = sum / 2; j >= arr[i]; j--) {
dep[j] = Math.max(dep[j], dep[j - arr[i]] + arr[i]);
}
}
// dfs(0,sum/2,dep,arr);
if (dep[sum / 2] == (sum / 2)) {
max=sum/2;
}
return max;
}
public static int dfs(int i,int j,int[] dp,int[] arr){
if(dp[j]>0)
return dp[j];
int res;
if(i==arr.length){
res=0;
}else if(j<arr[i]){
res=dfs(i+1,j,dp,arr);
}else{
res=Math.max(dfs(i+1,j,dp,arr),dfs(i+1,j-arr[i],dp,arr)+arr[i]);
}
return dp[j]=res;
}
*/
}
結果
分餅干
易老師購買了一盒餅干殴瘦，盒子中一共有k塊餅干，但是數(shù)字k有些數(shù)位變得模糊了号杠，看不清楚數(shù)字具體是多少了蚪腋。易老師需要你幫忙把這k塊餅干平分給n個小朋友丰歌，易老師保證這盒餅干能平分給n個小朋友。現(xiàn)在你需要計算出k有多少種可能的數(shù)值
輸入描述:
輸入包括兩行：
第一行為盒子上的數(shù)值k屉凯，模糊的數(shù)位用X表示立帖，長度小于18(可能有多個模糊的數(shù)位)
第二行為小朋友的人數(shù)n
輸出描述:
輸出k可能的數(shù)值種數(shù)，保證至少為1
輸入例子1:
9999999999999X
3
輸出例子1:
4
解題思路
暴力法超時.同樣使用動態(tài)規(guī)劃
dp[i][j]表示前i個數(shù)字余數(shù)為j時可能的數(shù)值種數(shù)
dp[0][0]=1 沒有數(shù)字且余數(shù)為0只有一種可能
狀態(tài)轉移方程為
dp[i][(j*10+k)%n]+=dp[i][j]
import java.util.Scanner;
public class Q12 {
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
String s=scanner.nextLine();
int n=scanner.nextInt();
long []dp=new long[n];
dp[0]=1;
for(int i=1;i<=s.length();i++){
long []temp= new long[n];
char c=s.charAt(i-1);
for(int j=0;j<n;j++){
for(int k=0;k<10;k++){
if(c=='X'||(c=='0'+k)){
temp[(j*10+k)%n]+=dp[j];
}
}
}
dp=temp;
}
System.out.print(dp[0]);
}
}
