其實心裡有些小小的不爽又有點小小的舒暢，為啥捏？不爽當然是因為沒被選拔上啦，舒暢捏則是因為沒被選拔上反而讓自己警醒，學長也提點很多很多。“沉下去，然後一戰成名”學長如是對我說，我很開心。其實這完全算不算是題解，只是我個人的一些小想法而已。而且到現在還有一題不會...讓自己長點記性吧。
Time Limit: 1 Sec Memory Limit: 128 MB Description 田鼠MIUMIU來到了一片農田，農田可以看成是一個M*N個方格的矩陣。每個方格裡放有一定的糧食。
MIUMIU看到這裡，興奮不已，它要拿走多多的糧食，以備過冬。但MIUMIU要麼往前走（向右） ，
要麼往下走。 但它很聰明，一定會找到一條拿走最多糧食的路徑。 MIUMIU目前在入口位置, 坐標為（1,1），出口位置在坐標（M,N）。 請你編程，計算一下當MIUMIU走出農田時,最多能拿走多少糧食。 Input 第一行： M N （ 1≤M ,N ≤50 ） 接下來有M行， 每行有N個整數,分別表示方格中的糧食數 0≤ Aij≤100 (i=1,..M, j=1,…N)
（所有的數之間有一個空格） Output 一個整數，表示MIUMIU能拿走的最多糧食數。 Sample Input 4 3 5 3 7 5 3 2 5 5 5 6 2 5 Sample Output 30 HINT Source
如諾手機查看代碼不好看請轉：http://paste.ubuntu.com/24387705/
1 #include <bits/stdc++.h>
2
3
4 using namespace std;
5 const int maxn=105;
6 int dp[maxn][maxn];
7 int a[maxn][maxn];
8 int Dp(int m,int n)
9 {
10 for(int i=m-1;i>=0;i--)
11 {
12 for(int j=n-1;j>=0;j--)
13 {
14 dp[i][j]=max(dp[i+1][j],dp[i][j+1])+a[i][j];
15 }
16 }
17 return dp[0][0];
18 }
19 int main()
20 {
21 int m,n;
22 cin>>m>>n;
23 for(int i=0;i<m;i++)
24 {
25 for(int j=0;j<n;j++)
26 {
27 cin>>a[i][j];
28 }
29 }
30 cout<<Dp(m,n)<<endl;
31 return 0;
32 }
Time Limit: 1 Sec Memory Limit: 128 MB Description Dr.Kong有一個容量為N MB (1 <= N <= 50,000)的存儲磁盤,不妨設地址空間編號為1到N。現在他需要安裝一些軟件，
每個軟件要占用一定大小的容量且必須裝在連續的地址空間裡。比如發出指令“1 100”，表示需要申請100 MB的存儲空間。
如果有多個滿足條件的連續空間，則選擇起始地址最小的一個進行分配。若沒有足夠的連續空間，將不安裝此軟件（即使有
足夠多的不連續存儲空間）。系統可以不定時的卸載軟件，釋放磁盤的空間。比如：發出“2 23 100”，表示釋放起始地址
為23的連續100MB大小的容量。釋放時，不需要考慮這些空間裡是否安裝過軟件。 請你編寫一個程序，幫助Dr.Kong處理M (1 <= M <= 50,000)個按指令次序請求的任務。第一個請求到來前，磁盤是空的。 Input 第1行: N M 第2…M+1行: 每行描述了一個請求，如果是申請，則用2個數字 1 Mi 表示； 如果是釋放，則用3個數字 2 Di Mi表示。數據之間用一個空格隔開. （1<=Di ,Mi<= 50,000） Output 對於每個申請指令，輸出占1行。如果請求能被滿足，輸出滿足條件的最小起始地址；如果請求無法被滿足，輸出0。對於每個釋放指令，不產生輸出。 Sample Input 10 6 1 3 1 3 1 3 1 3 2 5 5 1 6 Sample Output 1 4 7 0 5
如諾手機查看代碼不好看請轉：http://paste.ubuntu.com/24387736/
1 #include <bits/stdc++.h>
2
3 using namespace std;
4 const int maxn=50005;
5 set<int> mem;//標記所有起始空閒地址
6 set<int>::iterator it;
7 int kx[maxn+1];//所有空閒起始地址的空閒空間
8 set<int> kxcs[20]; //分別存儲所有長度大於等於p[i]的起始地址
9 const int p[20]={1,2,3,4,5,6,7,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};//分組
10 pair<set<int>::const_iterator,set<int>::const_iterator> pr;
11 void insertit(int insertcs,int len);
12 void deleteit(int deletecs);
13 int lg2(int len)
14 {
15 int getit;
16 int i=0;
17 for(;p[i]<=len&&i<20;i++);
18 getit=i-1;
19 return getit;
20 }
21 int searchit(int len)//查找
22 {
23 int addr=lg2(len);//選擇入口
24 set<int>::iterator itit;
25 for(itit=kxcs[addr].begin();itit!=kxcs[addr].end();itit++)//從入口開始遍歷
26 {
27 int getcs=*itit;
28 if(kx[getcs]>=len)
29 {
30 int afterlen=kx[getcs]-len;
31 int aftercs=getcs+len;
32 kx[aftercs]=afterlen;
33 deleteit(getcs);
34 if(afterlen!=0)
35 {
36 insertit(aftercs,afterlen);
37 }
38 return getcs;
39 }
40 }
41 return 0;
42 }
43 void insertit(int insertcs,int len)//添加 起始地址與長度
44 {
45 int addr=lg2(len);
46 mem.insert(insertcs);//更新總數據
47 kx[insertcs]=len;
48 for(int i=0;i<=addr;i++)//更新分組數據
49 {
50 kxcs[i].insert(insertcs);
51 }
52 /* for(set<int>::iterator itit=mem.begin();itit!=mem.end();itit++)
53 {
54 cout<<*itit<<endl;
55 }*/
56 }
57 void deleteit(int deletecs)
58 {
59 int addr=lg2(kx[deletecs]);
60 kx[deletecs]=0;
61 mem.erase(deletecs);
62 for(int i=0;i<=addr;i++)
63 {
64 kxcs[i].erase(deletecs);
65 }
66 }
67 int m,n,sta,di,mi;
68 int main()
69 {
70 memset(kx,0,sizeof(kx));
71 kx[maxn]=maxn;
72 scanf("%d %d",&n,&m);
73 mem.insert(0);
74 mem.insert(maxn);//用於保護，以免出現段錯誤
75 insertit(1,n);
76 while(m--)
77 {
78 scanf("%d",&sta);
79 if(sta==1)
80 {
81 scanf("%d",&mi);
82 printf("%d\n",searchit(mi));
83 }
84 else
85 {
86 scanf("%d %d",&di,&mi);
87 int flag=false;
88 int si=di;
89 if(si>n)continue;
90 int ei=di+mi-1;
91 if(ei>n)ei=n;//限制邊界
92 pr=mem.equal_range(di);//該函數可以從容器中返回第一個大於等於或大於指定數的數
93 it=pr.first;
94 it--;//往後一個即為最後一個比它小的
95 if(*it+kx[*it]-1>=ei&&*it+kx[*it]-1>=si-1)continue;//新區間直接被原先區間覆蓋，那該次釋放無意義
96 if(*it+kx[*it]-1>=si-1)//如果最後一個比它小的結束地址大於本次釋放區間起始地址，則這兩個區間將連起來，初始地址將是*it
97 {
98 si=*it;
99 deleteit(*(it++));//先刪除該區間，下面重建，因為還不知道區間長度
100 }
101 else it++;
102 while(true)
103 {
104 if(*it+kx[*it]-1>ei)//遍歷新的釋放空間會重合的所有區間，當某區間結束地址比新區間的結束地址大時遍歷結束
105 {
106 if(*it<=ei+1)//該區間與新區間相連接起來
107 {
108 ei=*it+kx[*it]-1;
109 deleteit(*it);//連接起來則全算為新區間的，把該區間刪除
110 }
111 insertit(si,ei-si+1);//把新區間加進去
112 break;
113 }
114 if(*it<=ei)
115 {
116 deleteit(*(it++));//區間起始地址小於等於新區間結束地址都是要和新區間重合的
117 }
118 else it++;
119 }
120 }
121 }
122 return 0;
123 }
Time Limit: 1 Sec Memory Limit: 128 MB Description Dr.Wu的寶寶1歲了，所以Dr.Wu准備買些積木給寶寶玩，促進孩子大腦的發育。由於寶寶太小，
所以他將高低不同的積木擺放的毫無規律（如圖A）。然而Dr.Wu發現，如果從當前的積木中抽走
一部分（圖B，C中虛線的即表示抽走的積木），剩下的積木能夠呈現出“V”形，即積木的高度先
嚴格遞減，然後嚴格遞增。圖B中，需要抽走三個積木，剩下的積木就可以呈現出“V”形，而圖C
中僅需抽走一根積木。Dr.Wu需要你幫忙找出最少抽走多少積木，剩下的積木就能呈現出“V”型？ Input 第一行： T 表示以下有T組測試數據（1≤T ≤8） 對每組測試數據： 第一行: N表示積木的個數。 （2<N<=100）， 第二行是空格隔開的N個正整數，每個正整數Hi表示第i個積木的高度（0<Hi<=10000）。 輸出中，僅一個數，即最少抽走的積木數。如果怎麼抽走積木都無法呈現出“V”形，則輸出“No Solution”。 Output 每組測試數據，輸出占一行，僅一個數，即最少抽走的積木數。如果怎麼抽走積木都無法呈現出“V”形，則輸出“No Solution”。 Sample Input 2 6 50 30 40 10 20 60 6 5 4 3 1 2 6 Sample Output 1 0
如諾手機查看代碼不好看請轉：http://paste.ubuntu.com/24387742/
#include <bits/stdc++.h>
using namespace std;
int shumu;
int jm[1050];
int b[1050];
int weizhi;
int res;
int maxv=1000000+7;
int ss()
{
int len=0;
b[0]=0;
for(int i=weizhi;i<shumu;i++)
{
if(jm[i]>b[len])
{
len++;
b[len]=jm[i];
}
else
{
for(int j=1;j<=len;j++)
{
if(jm[i]<=b[j])
{
b[j]=jm[i];
break;
}
}
}
}
return len;
}
int xj()
{
int len=0;
b[0]=maxv;
for(int i=0;i<weizhi+1;i++)
{
if(jm[i]<b[len])
{
len++;
b[len]=jm[i];
}
else
{
for(int j=1;j<=len;j++)
{
if(jm[i]>=b[j])//大於等於都換，否則長度算出來有問題
{
b[j]=jm[i];
break;
}
}
}
}
return len;
}
int main()
{
int T;
cin>>T;
for(int i=0;i<T;i++)
{
cin>>shumu;
int yc=0;
memset(jm,0,sizeof(jm));
for(int j=0;j<shumu;j++)
{
cin>>jm[j];
}
res=shumu;
for(int k=0;k<shumu;k++)
{
weizhi=k;
int m,n;
m=ss();n=xj();
if(m==1||n==1)
{
continue;
}
int u=shumu-m-n+1;
if(res>u)res=u;
}
if(res<shumu-2)
{
cout<<res<<endl;
}
else
{
cout<<"No Solution"<<endl;
}
}
return 0;
}
Time Limit: 2 Sec Memory Limit: 128 MB Description 某地區M座煤礦，其中第i號礦每年產量為Ai噸，現有火力發電廠一個，每年需用煤B噸，
每年運行的固定費用（包括折舊費，不包括煤的運費）為H元，每噸原煤從第i號礦運到
原有發電廠的運費為Ci0（i=1，2，…，M）。 現規劃新建一個發電廠，M座煤礦每年開采的原煤將全部供給這兩座發電廠。現有N個備選
的廠址。若在第j號備選廠址建新廠，每年運行的固定費用為Hj元。每噸原煤從第i號礦運
到j號備選廠址的運費為Cij（i=1，2，…，M；j=1，2，…，N）。 試問：應把新廠廠址選取在何處？M座煤礦開采的原煤應如何分配給兩個發電廠，才能使
每年的總費用（發電廠運行費用與原煤運費之和）為最小。
Input 第一行： T 表示以下有T組測試數據（1≤T ≤5） 對每組測試數據： 第1行： M B H N 第2行： A1 A2 … Am （0<=Ai<=500, A1+A2+...+An>=B） 第3行： H1 H2 … Hn （0<=Hi<=100） 第4行： C10 C20 … Cm0 第5行： C11 C21 … Cm1 … … 第n+4行： C1n C2n … Cmn （0<=Cij<=50） Output 每組測試數據，輸出占一行，兩個整數，即新廠址編號和總費用。如果有多個編號滿足要求，輸出最小的。 Sample Input 1 4 2 7 9 3 1 10 3 6 3 7 1 10 2 7 4 9 1 2 4 3 6 6 8 2 4 10 8 4 10 2 9 2 7 6 6 2 9 3 7 1 2 1 6 9 3 1 10 9 4 2 1 8 2 1 3 4 Sample Output 8 49
如諾手機查看代碼不好看請轉：http://paste.ubuntu.com/24387745/
1 #include <bits/stdc++.h>
2
3 using namespace std;
4 const int maxn=105;
5 struct Rem
6 {
7 int value;
8 int weight;
9 };
10 bool bmp(Rem a,Rem b)
11 {
12 return (a.value<b.value);
13 }
14 int temp=0;
15 int a[maxn];int h[maxn];
16 int c0[maxn];
17 int c[maxn];
18 Rem rem[maxn];
19 Rem rem0[maxn];
20 int m,b,H,n;
21 int main()
22 {
23 int T;
24 scanf("%d",&T);
25 while(T--)
26 {
27 temp=0;
28 int res=1000000000+7;
29 scanf("%d %d %d %d",&m,&b,&H,&n);
30 for(int i=1;i<=m;i++)
31 {
32 scanf("%d",&a[i]);
33 }
34 for(int i=1;i<=n;i++)
35 {
36 scanf("%d",&h[i]);
37 }
38 for(int i=1;i<=m;i++)
39 {
40 scanf("%d",&c0[i]);
41 }
42 int test=1;
43 int u=1,r=1;
44 int weight=0;
45 int needweight=0;
46 int num=0;
47 for(;test<=n;test++)
48 {
49 temp=0;weight=0;needweight=0;u=1;r=1;
50 for(int k=1;k<=m;k++)
51 {
52 scanf("%d",&c[k]);
53 if(c[k]<c0[k])
54 {
55 rem[u].value=c0[k]-c[k];
56 rem[u++].weight=a[k];
57 temp+=c[k]*a[k];
58 }
59 else
60 {
61 rem0[r].value=c[k]-c0[k];
62 rem0[r++].weight=a[k];
63 temp+=c0[k]*a[k];
64 weight+=a[k];
65 }
66 }
67 if(weight>=b)
68 {
69 sort(rem0+1,rem0+r,bmp);
70 needweight=weight-b;
71 for(int k=1;k<r;k++)
72 {
73 if(rem0[k].weight>=needweight)
74 {
75 temp+=needweight*rem0[k].value;
76 needweight=0;
77 break;
78 }
79 else
80 {
81 needweight-=rem0[k].weight;
82 temp+=rem0[k].value*rem0[k].weight;
83 }
84 }
85 if(res>temp+H+h[test])
86 {
87 res=temp+H+h[test];
88 num=test;
89 }
90 }
91 else
92 {
93 sort(rem+1,rem+u,bmp);
94 needweight=b-weight;
95 for(int k=1;k<u;k++)
96 {
97 if(rem[k].weight>=needweight)
98 {
99 needweight=0;
100 temp+=needweight*rem[k].value;
101 break;
102 }
103 else
104 {
105 needweight-=rem[k].weight;
106 temp+=rem[k].value*rem[k].weight;
107 }
108 }
109 if(res>temp+H+h[test])
110 {
111 res=temp+H+h[test];
112 num=test;
113 }
114 }
115 }
116 printf("%d %d\n",num,res);
117 }
118 return 0;
119 }
