//此節較難，不能急，後面5題最好一天做1~2題，好好琢磨。。吃透。想BFS那樣慢慢來 I題還是不怎麼了解。。。
目錄
問題 A: 第二題
問題 B: 攔截飛彈
問題 C: 合唱隊形
問題 D: Coincidence
問題 E: 最大子矩陣
問題 F: 放蘋果
問題 G: 點菜問題
問題 H: 最大報帳額
問題 I: 畢業bg
問題 A: 第二題
時間限制: 1 Sec 記憶體限制: 32 MB
送出: 167 解決: 3
[送出][狀态][讨論版][命題人:外部導入]
題目描述
一個數組中有若幹正整數，将此數組劃分為兩個子數組，使得兩個子數組各元素之和a,b的差最小，對于非法輸入應該輸出ERROR。
輸入
數組中的元素
輸出
降序輸出兩個子數組的元素和
樣例輸入
10 20 30 10 10
10 20 abc 10 10 樣例輸出
40 40
ERROR 不知道為何總是段錯誤，運作錯誤，甚至編譯錯誤，oj有問題
看出來這是一個01背包問題
對于一維寫法：
重量和價值數組都是a[i] （數組a存儲輸入的一列數字）
總體積V=sum/2 （sum是數組和）
求總重量不超過sum/2時的最大價值
#include<iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=10000000;
long long a[N],dp[N];
string ss;
int toArray(string ss){
int index=0,t=0;
int L=ss.length();
for(int i=0;i<L;i++){
if(isspace(ss[i])){
t=0;
continue;
}else if(isdigit(ss[i])){
while(isdigit(ss[i])){
t=t*10+(ss[i]-'0');
i++;
}
a[++index]=t;
t=0;
}else{
return -1;//含有非法字元
}
}
return index;
}
int main(){
while(getline(cin,ss)){
memset(a,0,sizeof(a));
memset(dp,0,sizeof(dp));
int sum=0;
int n=toArray(ss);//字元串轉數組 傳回長度
if(n==-1){
cout<<"ERROR\n";
continue;
}else{
for(int i=1;i<=n;i++) sum+=a[i];
for(int i=1;i<=n;i++){
for(int V=sum/2;V>=a[i];V--){//重量價值都是a[i]
dp[V]=max(dp[V],dp[V-a[i]]+a[i]);
}
}
}
cout<<dp[sum/2]<<" "<<sum-dp[sum/2]<<endl;
}
return 0;
} 問題 B: 攔截飛彈
時間限制: 1 Sec 記憶體限制: 32 MB
送出: 155 解決: 70
[送出][狀态][讨論版][命題人:外部導入]
題目描述
某國為了防禦敵國的飛彈襲擊，開發出一種飛彈攔截系統。但是這種飛彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以後每一發炮彈都不能高于前一發的高度。某天，雷達捕捉到敵國的飛彈來襲，并觀測到飛彈依次飛來的高度，請計算這套系統最多能攔截多少飛彈。攔截來襲飛彈時，必須按來襲飛彈襲擊的時間順序，不允許先攔截後面的飛彈，再攔截前面的飛彈。
輸入
每組輸入有兩行，第一行，輸入雷達捕捉到的敵國飛彈的數量k（k<=25），第二行，輸入k個正整數，表示k枚飛彈的高度，按來襲飛彈的襲擊時間順序給出，以空格分隔。
輸出
每組輸出隻有一行，包含一個整數，表示最多能攔截多少枚飛彈。
樣例輸入
4
9 6 7 8
7
4 5 6 7 13 42 3
5
6 5 4 3 5
0 樣例輸出
2
2
4 注意：以後每一發炮彈都不能高于前一發的高度，求最長不增子序列，不是最長遞減子序列，可以相等
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
// freopen("inputb.txt","r",stdin);
int k;
int a[30],dp[30];
while(cin>>k&&k){
for(int i=0;i<k;i++){
cin>>a[i];
}
for(int i=0;i<k;i++){
dp[i]=1;
for(int j=0;j<i;j++){
if(a[j]>=a[i]&&dp[j]+1>dp[i]){
dp[i]=dp[j]+1;
}
}
}
cout<<*max_element(dp,dp+k)<<endl;
}
return 0;
} 問題 C: 合唱隊形
時間限制: 1 Sec 記憶體限制: 32 MB
送出: 132 解決: 60
[送出][狀态][讨論版][命題人:外部導入]
題目描述
N位同學站成一排，音樂老師要請其中的(N-K)位同學出列，使得剩下的K位同學不交換位置就能排成合唱隊形。
合唱隊形是指這樣的一種隊形：設K位同學從左到右依次編号為1, 2, …, K，他們的身高分别為T1, T2, …, TK，
則他們的身高滿足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。
你的任務是，已知所有N位同學的身高，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形。
輸入
輸入的第一行是一個整數N（2 <= N <= 100），表示同學的總數。
第一行有n個整數，用空格分隔，第i個整數Ti（130 <= Ti <= 230）是第i位同學的身高（厘米）。
輸出
可能包括多組測試資料，對于每組資料，
輸出包括一行，這一行隻包含一個整數，就是最少需要幾位同學出列。
樣例輸入
3
174 208 219
6
145 206 193 171 187 167
0 樣例輸出
0
1 注意：1.相交處會多出一個人，要減1
2.求dp2[]最長遞減子序列要重後往前算，也即是dp2[i]表示以a[i]為開頭的最長遞減子序列的長度(而非一貫的結尾)
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
// freopen("inputc.txt","r",stdin);
int a[110],dp1[110],dp2[110],ans[110];
int n;
while(cin>>n&&n){
for(int i=0;i<n;i++){
cin>>a[i];
}
//最長遞增子序列
for(int i=0;i<n;i++){
dp1[i]=1;
for(int j=0;j<i;j++){
if(a[j]<a[i]&&dp1[j]+1>dp1[i]){
dp1[i]=dp1[j]+1;
}
}
}
//最長遞減子序列 要重後面往前算 也即是dp2[i]表示以i開頭(而非結尾)的最長遞減子序列長度
for(int i=n-1;i>=0;i--){
dp2[i]=1;
for(int j=n-1;j>i;j--){
if(a[j]<a[i]&&dp2[j]+1>dp2[i]){
dp2[i]=dp2[j]+1;
}
}
//現在就可以開始加ans了
ans[i]=dp1[i]+dp2[i]-1;//相交處重複了一個人
}
cout<<n-*max_element(ans,ans+n)<<endl;
}
return 0;
} 問題 D: Coincidence
時間限制: 1 Sec 記憶體限制: 32 MB
送出: 89 解決: 46
[送出][狀态][讨論版][命題人:外部導入]
題目描述
Find a longest common subsequence of two strings.
輸入
First and second line of each input case contain two strings of lowercase character a…z. There are no spaces before, inside or after the strings. Lengths of strings do not exceed 100.
輸出
For each case, output k – the length of a longest common subsequence in one line.
樣例輸入
google
goodbye 樣例輸出
4 #include<iostream>
#include<string>
#include<cstring>
#include <algorithm>
using namespace std;
int main(){
// freopen("inputd.txt","r",stdin);
string s1,s2;
int dp[110][110];
while(cin>>s1>>s2){
s1=" "+s1;
s2=" "+s2;
memset(dp,0,sizeof(dp));
for(int i=1;i<s1.length();i++){
for(int j=1;j<s2.length();j++){
if(s1[i]==s2[j]){
dp[i][j]=dp[i-1][j-1]+1;
}else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
cout<<dp[s1.length()-1][s2.length()-1]<<endl;
}
return 0;
} 問題 E: 最大子矩陣
時間限制: 1 Sec 記憶體限制: 32 MB
送出: 120 解決: 46
[送出][狀态][讨論版][命題人:外部導入]
題目描述
已知矩陣的大小定義為矩陣中所有元素的和。給定一個矩陣，你的任務是找到最大的非空(大小至少是1 * 1)子矩陣。
比如，如下4 * 4的矩陣
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
的最大子矩陣是
9 2
-4 1
-1 8
這個子矩陣的大小是15。
輸入
輸入是一個N * N的矩陣。輸入的第一行給出N (0 < N <= 100)。
再後面的若幹行中，依次（首先從左到右給出第一行的N個整數，再從左到右給出第二行的N個整數……）給出矩陣中的N2個整數，整數之間由空白字元分隔（空格或者空行）。
已知矩陣中整數的範圍都在[-127, 127]。
輸出
測試資料可能有多組，對于每組測試資料，輸出最大子矩陣的大小。
樣例輸入
1
27
3
-40 29 -16
38 18 22
24 -35 5 樣例輸出
27
78 最大子序列問題的二維形式
累加各列轉換為一維形式。累加列後能保證結果各列長度連續一緻，但是行呢？最終結果到底那幾行？枚舉所有連續行相加的情況即可
枚舉第i行到第j行相加得到的數組
例如共4行分别累加 123表示累加1 2 3行各列
1 12 123 1234
2 23 234
3 34
4 每次都得到dp[4]的數組 表示累加的行各列的和
再橫向一維求最大子序列和即可
以i行到j行為累加分法 累加的是列值
注意：Max初值不能是0 要是a[0][0]否則這種資料過不了 a[0][0]才是二維形式最大子序列和的初始狀況 類似一維dp[0]=a[0]
2
-1 -1
-1 -1
#include<iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n,a[110][110],dp[110],Max;
//一維最大子序列和(連續)
int max_sub(int a[]){
int dp[101];
dp[0]=a[0];
for(int i=1;i<n;i++){
if(dp[i-1]>0){
dp[i]=dp[i-1]+a[i];
}else{
dp[i]=a[i];
}
}
return *max_element(dp,dp+n);
}
int main(){
freopen("inpute.txt","r",stdin);
while(cin>>n){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>a[i][j];
}
}
Max=a[0][0];//注意
for(int i=0;i<n;i++){//起始行
memset(dp,0,sizeof(dp));
//起始行到後面每一行都累加一次求一次
for(int j=i;j<n;j++){//累加i~j行各列 (第一次i~i就是第i行)
for(int k=0;k<n;k++){//累加各列
dp[k]+=a[j][k];
}
//此時dp是i~j行豎向各列值之和
int temp=max_sub(dp);
if(Max<temp) Max=temp;
}
}
cout<<Max<<endl;
}
return 0;
} 問題 F: 放蘋果
時間限制: 1 Sec 記憶體限制: 32 MB
送出: 55 解決: 45
[送出][狀态][讨論版][命題人:外部導入]
題目描述
把M個同樣的蘋果放在N個同樣的盤子裡，允許有的盤子空着不放，問共有多少種不同的分法？（用K表示）5，1，1和1，5，1 是同一種分法。
輸入
第一行是測試資料的數目t（0 <= t <= 20）。以下每行均包含二個整數M和N，以空格分開。1<=M，N<=10。
輸出
對輸入的每組資料M和N，用一行輸出相應的K。
樣例輸入
2
6 3
7 2 樣例輸出
7
4 解題分析：
設f(m,n) 為m個蘋果，n個盤子的放法數目，則先對n作讨論，
當n>m： 必定有n-m個盤子永遠空着，去掉它們對擺放蘋果方法數目不産生影響(因為擺放順序無影響)。
即if(n>m) f(m,n) = f(m,m)
當n<=m：不同的放法可以分成兩類：
1、有至少一個盤子空着，即相當于f(m,n) = f(m,n-1);
了解2：有空盤子很多人會有疑問，這不是隻有一個空盤子的情況嗎？那2個3個空盤子呢？這就需要遞歸的思想，
随着一步一步的将n換成n-1你就會發現那就是2,3個空盤子的情況。
2、所有盤子都有蘋果，相當于可以從每個盤子中拿掉一個蘋果，不影響不同放法的數目，即f(m,n) = f(m-n,n)
了解2:沒有空盤子，我們可以看成先給每一個盤子放一個蘋果，則還剩下m-n個蘋果，剩下的問題就是把這m-n個
蘋果放到n個盤子裡的問題了，也許有人會問，m-n個蘋果放到n個盤子也會出現空盤子的情況啊，不是和前面
的有空盤子重複了？确實，會出現空盤子的情況，但是請注意，他們并不是真的空盤子，因為他們最開始已經
放了一個，他們在這裡的空代表着這個盤子隻有最開始放的一個蘋果。
而總的放蘋果的放法數目等于兩者的和，即
f(m,n) =f(m,n-1)+f(m-n,n)
遞歸出口條件說明：
當n=1時，所有蘋果都必須放在一個盤子裡，是以傳回１；
當沒有蘋果可放時，定義為１種放法；
遞歸的兩條路，第一條n會逐漸減少，終會到達出口n==1;
第二條m會逐漸減少，因為n>m時，我們會return f(m,m) 是以終會到達出口m==0．
#include<iostream>
#include<stdio.h>
using namespace std;
int DivNum(int m,int n){
//n>=m往下遞歸 n最小為1 則m可能為0
if(n==1||m==0) return 1;
if(m<n) return DivNum(m,m);
else{ //有空 n不斷-1 所有空的情況都考慮了
return DivNum(m,n-1)+DivNum(m-n,n);
//無空:先每個盤子放一個即可保證
}
}
int main(){
// freopen("inputf.txt","r",stdin);
int T,m,n;
cin>>T;
while(T--){
cin>>m>>n;
cout<<DivNum(m,n)<<endl;
}
// system("pause");
return 0;
} 問題 G: 點菜問題
時間限制: 1 Sec 記憶體限制: 32 MB
送出: 100 解決: 58
[送出][狀态][讨論版][命題人:外部導入]
題目描述
北大網絡實驗室經常有活動需要叫外買，但是每次叫外買的報帳經費的總額最大為C元，有N種菜可以點，經過長時間的點菜，網絡實驗室對于每種菜i都有一個量化的評價分數（表示這個菜可口程度），為Vi，每種菜的價格為Pi, 問如何選擇各種菜，使得在報帳額度範圍内能使點到的菜的總評價分數最大。
注意：由于需要營養多樣化，每種菜隻能點一次。
輸入
輸入的第一行有兩個整數C（1 <= C <= 1000）和N（1 <= N <= 100），C代表總共能夠報帳的額度，N>代表能點菜的數目。接下來的N行每行包括兩個在1到100之間（包括1和100）的的整數，分别表示菜的>價格和菜的評價分數。
輸出
輸出隻包括一行，這一行隻包含一個整數，表示在報帳額度範圍内，所點的菜得到的最大評價分數。
樣例輸入
1 3
1 5
3 3
2 5
24 8
2 9
8 6
4 1
1 4
2 2
10 5
2 1
1 4 樣例輸出
5
30 典型01背包問題
注意：(1)價值最大1000 dp數組長度1010而不是110 (2)背包問題下标都從1開始 0都是邊界
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int C,N;
int c[110],w[110];//價格和評分
int dp[1010];//c在1000以内 dp[c]下标是價值 要定義成1010 而不是110 因為下标問題 卡住這麼久。。。。
int main(){
// freopen("inputg.txt","r",stdin);
while(cin>>C>>N){
memset(dp,0,sizeof(dp));
//背包問題要從1開始，因為邊界是dp[0][j]=0 dp[i][0]=0
for(int i=1;i<=N;i++){
cin>>c[i]>>w[i];
}
for(int i=1;i<=N;i++){
for(int j=C;j>=c[i];j--){
dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
}
}
cout<<dp[C]<<endl;
}
return 0;
} 問題 H: 最大報帳額
時間限制: 1 Sec 記憶體限制: 32 MB
送出: 236 解決: 7
[送出][狀态][讨論版][命題人:外部導入]
題目描述
現有一筆經費可以報帳一定額度的發票。允許報帳的發票類型包括買圖書（A類）、文具（B類）、差旅（C類），要求每張發票的總額不得超過1000元，每張發票上，單項物品的價值不得超過600元。現請你編寫程式，在給出的一堆發票中找出可以報帳的、不超過給定額度的最大報帳額。
輸入
測試輸入包含若幹測試用例。每個測試用例的第1行包含兩個正數 Q 和 N，其中 Q(Q<=2000) 是給定的報帳額度，N（N<=30）是發票張數。随後是 N 行輸入，每行的格式為：
m Type_1:price_1 Type_2:price_2 ... Type_m:price_m
其中正整數 m 是這張發票上所開物品的件數，Type_i 和 price_i 是第 i 項物品的種類和價值。物品種類用一個大寫英文字母表示。當N為0時，全部輸入結束，相應的結果不要輸出。
輸出
對每個測試用例輸出1行，即可以報帳的最大數額，精确到小數點後2位。
樣例輸入
300.00 3
2 A:33.50 B:150.00
1 C:850.00
3 A:159.99 A:350.00 X:10.00
1100.00 2
2 B:600.00 A:400.00
1 C:300.50
150.00 0 樣例輸出
183.50
1000.00 提示
首先要按照題目的要求計算後判斷每張發票的有效性，接着是一個動态規劃算法（沒見過類似題目的同學可以搜一下“背包問題”），對于此題，由于題目交代了所有金額都隻到小數點後兩位，是以乘以100後即是整數，進而可以轉化為01背包問題，用dp[i]表示到達總金額為i的有效性。
注:
★1.将價格*1000轉換為整數繼而才可以用01背包來解決問題 (注意此時數組下标也要擴大1000倍)
保留2位小數 看似*100就行了 但是測試資料似乎有3位小數的情況，那麼由于舍入原因*100強制将double指派給int就 會有誤差
(最大的坑。。。不知道價格小數點後3位是何意義。*100錯誤50%)
且：為了減少誤差，一開始都當double來處理，直到dp之前才開始*1000轉換為int
2.題目對每張發票有3層限制
1)單項物品價值超過600的發票無效
2)總價值超過1000的發票無效
3)買了非A、B、C類物品的發票無效
發票無效即不給報帳(誰叫你瞎買呢?)
3.單項物品價值不得超過600,指的就是一個物品，而不是一類物品
4.代碼31行後千萬不能寫break,雖然已經知道了此張發票不合法，但是輸入卻沒有結束，必須老老實實接收完所有的輸 入，否則疊加到下次輸入就錯了
低級錯誤： (int)pf[i]*TIMES 真實含義是((int)pf[i])*TIMES 正确寫法(int)(pf[i]*TIMES)
ac代碼：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
//TIMES=100 錯誤50%
const int TIMES=1000;//防止四舍五入等誤差 輸入可能不一定是2位小數 轉化為整數一定最後再轉，先轉會積累誤差
double pf[35];//原始小數價格
int p[35];//價格 既是價值，又是重量
int dp[3000*TIMES+10];
int Q,N;
int main(){
// freopen("inputh.txt","r",stdin);
double sumP;//sumP總可報帳價值
int index;//合法發票數量
int m;//本張發票物品總數
double total,pri;//發票總價和單個物品價格
char c1,c2;
while(cin>>sumP>>N&&N){
index=0;
for(int i=1;i<=N;i++){
bool flag=true;
cin>>m;
total=0;
for(int j=0;j<m;j++){//也用了i 與外層循環重複了。。。
cin>>c1>>c2;//占位符 其實不用理睬他是哪一類的
cin>>pri;
if(pri>600||(c1!='A'&&c1!='B'&&c1!='C')) {
flag=false;//不能break,因為要接收完每次所有的輸入。。。。
}
total+=pri;
}
if(flag&&(total<=1000)){
pf[++index]=total;
}
}
memset(dp,0,sizeof(dp));
memset(p,0,sizeof(p));
for(int i=1;i<=index;i++){
p[i]=pf[i]*TIMES;//轉換為整數 現在一起轉 才不會有誤差 不要強轉pf[i] (int)pf[i]*TIMES會出錯 僅僅強轉了pf
}
Q=sumP*TIMES;//保留2位小數 *100就能做下标用dp來處理了 防止舍入誤差*1000
for(int i=1;i<=index;i++){
for(int v=Q;v>=p[i];v--){
dp[v]=max(dp[v],dp[v-p[i]]+p[i]);
}
}
printf("%.2lf\n",dp[Q]*1.0/TIMES);//1.0必須要乘 因為dp[Q]和TIMES都是int型
}
return 0;
} 問題 I: 畢業bg
時間限制: 1 Sec 記憶體限制: 32 MB
送出: 143 解決: 47
[送出][狀态][讨論版][命題人:外部導入]
題目描述
每 年畢業的季節都會有大量畢業生發起狂歡，好朋友們相約吃散夥飯，網絡上稱為“bg”。參加不同團體的bg會有不同的感覺，我們可以用一個非負整數為每個 bg定義一個“快樂度”。現給定一個bg清單，上面列出每個bg的快樂度、持續長度、bg發起人的離校時間，請你安排一系列bg的時間使得自己可以獲得最 大的快樂度。
例如有4場bg：
第1場快樂度為5，持續1小時，發起人必須在1小時後離開；
第2場快樂度為10，持續2小時，發起人必須在3小時後離開；
第3場快樂度為6，持續1小時，發起人必須在2小時後離開；
第4場快樂度為3，持續1小時，發起人必須在1小時後離開。
則獲得最大快樂度的安排應該是：先開始第3場，獲得快樂度6，在第1小時結束，發起人也來得及離開；再開始第2場，獲得快樂度10，在第3小時結束，發起人正好來得及離開。此時已經無法再安排其他的bg，因為發起人都已經離開了學校。是以獲得的最大快樂度為16。
注意bg必須在發起人離開前結束，你不可以中途離開一場bg，也不可以中途加入一場bg。
又因為你的人緣太好，可能有多達30個團體bg你，是以你需要寫個程式來解決這個時間安排的問題。
輸入
測試輸入包含若幹測試用例。每個測試用例的第1行包含一個整數N (<=30)，随後有N行，每行給出一場bg的資訊：
h l t
其中 h 是快樂度，l是持續時間（小時），t是發起人離校時間。資料保證l不大于t,因為若發起人必須在t小時後離開，bg必須在主人離開前結束。
當N為負數時輸入結束。
輸出
每個測試用例的輸出占一行，輸出最大快樂度。
樣例輸入
3
6 3 3
3 2 2
4 1 3
4
5 1 1
10 2 3
6 1 2
3 1 1
-1 樣例輸出
7
16 //背包還是不怎麼了解。。。。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
//dp[i]表示發起人必須在i點離開時能獲得的最大歡樂度
struct bg{
int h,l,t;//快樂度、持續時間、發起人離校時間
}A[35];
bool cmp(bg b1,bg b2){
return b1.t<b2.t;//按照離校時間排序
}
int main(){
// freopen("inputI.txt","r",stdin);
int N;
int dp[100000];//不能定義太大了
while(cin>>N&&N>0){
memset(dp,0,sizeof(dp));
int sum=0;
for(int i=0;i<N;i++){
cin>>A[i].h>>A[i].l>>A[i].t;
if(sum<A[i].t) sum=A[i].t;
}
sort(A,A+N,cmp);
int MAX=0;
for(int i=0;i<N;i++){
for(int j=A[i].t;j>=A[i].l;j--){//0~1 背包 先排序 再t~l 再最大
dp[j]=max(dp[j],dp[j-A[i].l]+A[i].h);
if(MAX<dp[j]) MAX=dp[j];//不一定dp[sum]最大。。。
}
}
cout<<MAX<<endl;
}
return 0;
}