置頂隨筆
#
更換blog ，因?yàn)樘厥庠?
http://www.cnblogs.com/sephirothlee/
2010年9月11日
#
更換blog ，因?yàn)樘厥庠?
http://www.cnblogs.com/sephirothlee/
2010年9月7日
#
今天用差不多半天的時間把WIN7裝好了，太累人了。
顯卡還是太垃圾…… 等放假去賓館卸一個回來！！……（有點(diǎn)不好的說）
1G的內(nèi)存，占用量一直在54%左右。確實(shí)很吃硬件。
2010年9月4日
#
今天上午是搜索。
- 最少乘法次數(shù)
- 彩票問題
- 黑白棋游戲
- pku1729
- 多處理機(jī)調(diào)度問題
- 魔盤
- 最短編號序列
- 任務(wù)安排
- 數(shù)字游戲(c&m)
- 埃及分?jǐn)?shù)
- antiprime
下午是數(shù)學(xué)的一些東西。
- 第二類string數(shù)
- 卡特蘭數(shù)
- polya原理
- 整數(shù)分解
- 極值問題
- Kathy函數(shù)
- 錯排問題
- 求Fibonacci數(shù)列
- 毛毛蟲
- 一序列
- 圓桌吃飯
- 01串問題
- 算術(shù)表達(dá)式的計(jì)算
2010年9月2日
#
時間
奔流。
本來是EVA的一個同人小說、某網(wǎng)友的ID?，F(xiàn)在突然有這種感覺了。
五天的集訓(xùn)，現(xiàn)在第三天就要結(jié)束了，明天就是3號。
4號，5號，6號回東區(qū)。然后猛補(bǔ)文化課，再有一個月，就開始最后的準(zhǔn)備了。
11月21日，上戰(zhàn)場的日子。
為了寶貝兒，為了我自己。
上午講的動態(tài)規(guī)劃的優(yōu)化。有很多經(jīng)典的例題。
- 寶物篩選
- 農(nóng)田個數(shù)
- 花店櫥窗布置
- 乘車路線
- 疊放箱子
- 演唱組
- divide
- 添加號
- 走道鋪磚問題
- 股票問題
- 火車票
- 殺螞蟻
- 瑰麗華爾茲
下午開始了搜索，有點(diǎn)暈。
- 走迷宮問題
- 訂貨單
- 計(jì)算機(jī)網(wǎng)絡(luò)連接
- N皇后
- Betsy’s tour
晚上好好休息。
【描述】
給一棵n個結(jié)點(diǎn)的樹，給每個點(diǎn)安排一個正整數(shù)編號，使得相鄰點(diǎn)具有不同的編號，編號的總和盡量小。
【輸入】
第一行：n(n<=50,000)
以下n-1行，每行兩個數(shù)u,v(1<=u,v<=n)，表示u 和v有一條邊
【輸出】
僅一行，為最小編號和
【樣例輸入】
8
1 2
1 3
1 4
1 5
5 6
5 7
5 8
【樣例輸出】
11
【分析】
f[i][j]表示i這個點(diǎn)標(biāo)j這個數(shù)所能到達(dá)的最小總值?？刂苆的范圍到30肯定過。
1: #include <stdio.h>
2: #include <iostream>
3: #define MAXINT 10000000
4: #define maxn 50010
5: using namespace std;
6:
7: int f[maxn][31];
8: int bl[maxn][maxn/100];
9: int son[maxn][maxn/100],root[maxn];
10: int n;
11: int x,y;
12: int ans=MAXINT;
13:
14: void maket(int x)
15: {
16: for (int i=1;i<=bl[x][0];++i)
17: {
18: int k=bl[x][i];
19: if (k==root[x]) continue;
20: son[x][++son[x][0]]=k;
21: root[k]=x;
22: maket(k);
23: }
24: }
25:
26: void dp(int x)
27: {
28: if (f[x][1]) return;
29: for (int i=1;i<=30;++i)
30: {
31: for (int j=1;j<=son[x][0];++j)
32: {
33: int tt=son[x][j];
34: dp(tt);
35: int minn=MAXINT;
36: for (int jj=1;jj<=30;++jj)
37: if (jj!=i)
38: if (f[tt][jj]<minn)
39: minn=f[tt][jj];
40: f[x][i]+=minn;
41: }
42: f[x][i]+=i;
43: }
44: }
45:
46: int main()
47: {
48: freopen("gems.in","r",stdin);
49: freopen("gems.out","w",stdout);
50:
51: scanf("%d",&n);
52: for (int i=1;i<n;++i)
53: {
54: scanf("%d%d",&x,&y);
55: bl[x][++bl[x][0]]=y;
56: bl[y][++bl[y][0]]=x;
57: }
58: maket(1);
59: dp(1);
60: for (int i=1;i<=30;++i)
61: if (f[1][i]<ans)
62: ans=f[1][i];
63: printf("%d\n",ans);
64: return 0;
65: }
66:
【問題描述】
太平王世子事件后，陸小鳳成了皇上特聘的御前一品侍衛(wèi)。
皇宮以午門為起點(diǎn)，直到后宮嬪妃們的寢宮，呈一棵樹的形狀；某些宮殿間可以互相望見。大內(nèi)保衛(wèi)森嚴(yán)，三步一崗，五步一哨，每個宮殿都要有人全天候看守，在不同的宮殿安排看守所需的費(fèi)用不同。
可是陸小鳳手上的經(jīng)費(fèi)不足，無論如何也沒法在每個宮殿都安置留守侍衛(wèi)。
幫助陸小鳳布置侍衛(wèi)，在看守全部宮殿的前提下，使得花費(fèi)的經(jīng)費(fèi)最少。
【數(shù)據(jù)輸入】
輸入數(shù)據(jù)由文件名為INPUT.TXT的文本文件提供。輸入文件中數(shù)據(jù)表示一棵樹，描述如下：
第1行 n，表示樹中結(jié)點(diǎn)的數(shù)目。
第2行至第n+1行，每行描述每個宮殿結(jié)點(diǎn)信息，依次為：該宮殿結(jié)點(diǎn)標(biāo)號i（0<i<=n），在該宮殿安置侍衛(wèi)所需的經(jīng)費(fèi)k，該邊的兒子數(shù)m，接下來m個數(shù)，分別是這個節(jié)點(diǎn)的m個兒子的標(biāo)號r1，r2，...，rm。
對于一個n（0 < n <= 1500）個結(jié)點(diǎn)的樹，結(jié)點(diǎn)標(biāo)號在1到n之間，且標(biāo)號不重復(fù)。
【數(shù)據(jù)輸出】
輸出到OUTPUT.TXT文件中。輸出文件僅包含一個數(shù)，為所求的最少的經(jīng)費(fèi)。
輸入數(shù)據(jù)示例 輸出數(shù)據(jù)示例
25
【分析】
分別用f[i][0]表示i點(diǎn)放看守，f[i][1]表示i點(diǎn)不放看守i點(diǎn)被兒子監(jiān)視，f[i][2]表示i點(diǎn)不放看守i點(diǎn)被父節(jié)點(diǎn)監(jiān)視三個情況下的最小費(fèi)用。
f[i][0]=所有子節(jié)點(diǎn)t的f[t][0],f[t][1],f[t][2]中最小的一個的合+k[i]
f[i][1]=某個子節(jié)點(diǎn)放看守+其他節(jié)點(diǎn)的f[t][0],f[t][1]中最小的一個的合
f[i][2]=所有子節(jié)點(diǎn)的f[t][1]的合
1: #include <stdio.h>
2: #include <iostream>
3: #define maxn 1510
4: #define MAXINT 10000000
5: using namespace std;
6:
7: int son[maxn][maxn];
8: int m[maxn];
9: int n,x;
10: int k[maxn];
11: int tem[maxn];
12: bool ro[maxn];
13: int v;
14: int f[maxn][3];
15:
16: void dp(int x)
17: {
18: if (f[x][0]) return;
19: for (int i=1;i<=m[x];++i)
20: {
21: int t=son[x][i];
22: dp(t);
23: f[x][0]+=min(f[t][0],min(f[t][1],f[t][2]));
24: f[x][2]+=f[t][1];
25: }
26: f[x][0]+=k[x];
27: memset(tem,0,sizeof(tem));
28: int tot=0;
29: for (int i=1;i<=m[x];++i)
30: {
31: int t=son[x][i];
32: tem[i]=min(f[t][0],f[t][1]);
33: tot+=tem[i];
34: }
35: f[x][1]=MAXINT;
36: for (int i=1;i<=m[x];++i)
37: {
38: int t=son[x][i];
39: if (tot-tem[i]+f[t][0]<f[x][1]) f[x][1]=tot-tem[i]+f[t][0];
40: }
41: }
42:
43: int main()
44: {
45: freopen("guard.in","r",stdin);
46: freopen("guard.out","w",stdout);
47:
48: scanf("%d",&n);
49: for (int i=1;i<=n;++i)
50: {
51: scanf("%d",&x);
52: scanf("%d%d",&k[x],&m[x]);
53: for (int j=1;j<=m[x];++j)
54: {
55: scanf("%d",&son[x][j]);
56: ro[son[x][j]]=1;
57: }
58: }
59: for (int i=1;i<=n;++i)
60: if (!ro[i])
61: {
62: v=i;
63: break;
64: }
65: //for (int i=1;i<=n;++i)
66: //f[i][2]=f[i][1]=MAXINT;
67: dp(v);
68: printf("%d\n",min(f[v][0],f[v][1]));
69: return 0;
70: }
71:
題目見ural1039
1: #include <stdio.h>
2: #include <stdlib.h>
3: #include <iostream>
4: #define maxn 6010
5: using namespace std;
6:
7: struct ss
8: {
9: int ro,nu;
10: } a[maxn];
11: int w[maxn];
12: int f[maxn][2];
13: int n;
14: int x,y;
15: int t[maxn];
16:
17: int cmp(const void*a,const void*b)
18: {
19: ss c=*(ss*)a,d=*(ss*)b;
20: if (c.ro<d.ro) return -1;
21: if (c.ro>d.ro) return 1;
22: return 0;
23: }
24:
25: void dp(int x)
26: {
27: if (f[x][1]) return;
28: for (int i=t[x];i<t[x+1];++i)
29: {
30: int k=a[i].nu;
31: dp(k);
32: f[x][1]+=f[k][0];
33: f[x][0]+=max(f[k][0],f[k][1]);
34: }
35: f[x][1]+=w[x];
36: }
37:
38: int main()
39: {
40: freopen("party.in","r",stdin);
41: freopen("party.out","w",stdout);
42:
43: scanf("%d",&n);
44: for (int i=1;i<=n;++i) scanf("%d",&w[i]);
45: scanf("%d%d",&x,&y);
46: while (!((!x)&&(!y)))
47: {
48: a[x].nu=x;
49: a[x].ro=y;
50: scanf("%d%d",&x,&y);
51: }
52: for (int i=1;i<=n;++i)
53: if (!a[i].ro)
54: a[i].nu=i;
55: a[0].ro=-1;
56: qsort(a,n+1,sizeof(ss),cmp);
57: for (int i=1;i<=n;++i)
58: if (!t[a[i].ro])
59: t[a[i].ro]=i;
60: t[n+1]=n+1;
61: for (int i=n;i>0;--i)
62: if (!t[i])
63: t[i]=t[i+1];
64: dp(0);
65: printf("%d\n",max(f[0][1],f[0][0]));
66: return 0;
67: }
68:
【描述】
N個任務(wù)排成一個序列在一臺機(jī)器上等待完成（順序不得改變），這N個任務(wù)被分成若干批，每批包含相鄰的若干任務(wù)。從時刻0開始，這些任務(wù)被分批加工，第i個任務(wù)單獨(dú)完成所需的時間是Ti。在每批任務(wù)開始前，機(jī)器需要啟動時間S，而完成這批任務(wù)所需的時間是各個任務(wù)需要時間的總和（同一批任務(wù)將在同一時刻完成）。每個任務(wù)的費(fèi)用是它的完成時刻乘以一個費(fèi)用系數(shù)Fi。請確定一個分組方案，使得總費(fèi)用最小。 例如：S=1；T={1,3,4,2,1}；F={3,2,3,3,4}。如果分組方案是{1,2}、{3}、{4,5}，則完成時間分別為{5,5,10,14,14}，費(fèi)用C{15,10,30,42,56}，總費(fèi)用就是153。
【輸入】
第一行是N(1<=N<=5000)。 第二行是S(0<=S<=50)。 下面N行每行有一對數(shù)，分別為Ti和Fi，均為不大于100的正整數(shù)，表示第i個任務(wù)單獨(dú)完成所需的時間是Ti及其費(fèi)用系數(shù)Fi。
【輸出】
一個數(shù)，最小的總費(fèi)用。
【樣例】
| BATCH.IN | BATCH.OUT |
5
1
1 3
3 2
4 3
2 3
1 4 | 153 |
【分析】
dp[i]：完成工作1到工作I的費(fèi)用+因增加S從I到N增加的費(fèi)用的總和的最小費(fèi)用。
dp[i]=min{dp[k-1]+s*(f[n]-f[k-1])+t[i]*(f[i]-f[k-1])}
1: #include <stdio.h>
2: #include <iostream>
3: #define MAXINT 10000000
4: #define maxn 5010
5: using namespace std;
6:
7: int n,s;
8: int t[maxn],f[maxn],dp[maxn];
9: int tem;
10:
11: int main()
12: {
13: freopen("batch.in","r",stdin);
14: freopen("batch.out","w",stdout);
15:
16: scanf("%d%d",&n,&s);
17: for (int i=1;i<=n;++i)
18: {
19: scanf("%d%d",&t[i],&f[i]);
20: t[i]+=t[i-1];
21: f[i]+=f[i-1];
22: }
23: for (int i=1;i<=n;++i) dp[i]=MAXINT;
24: dp[0]=0;
25: for (int i=1;i<=n;++i)
26: for (int k=1;k<=i;++k)
27: {
28: tem=dp[k-1]+s*(f[n]-f[k-1])+t[i]*(f[i]-f[k-1]);
29: if (tem<dp[i]) dp[i]=tem;
30: }
31: printf("%d\n",dp[n]);
32: return 0;
33: }
34:
【描述】
多瑞卡得到了一份有趣而高薪的工作。每天早晨他必須關(guān)掉他所在村莊的街燈。所有的街燈都被設(shè)置在一條直路的同一側(cè)。
多瑞卡每天到早晨5點(diǎn)鐘都按時起床，然后他開始關(guān)燈。開始時，他站在某一盞路燈的旁邊。
每盞燈都有一個給定功率的電燈泡，因?yàn)槎喽丝ㄓ兄杂X的節(jié)能意識，他希望在耗電能總數(shù)最少的情況下將所有的燈關(guān)掉。
多端卡因?yàn)樘哿耍灾荒芤?m/s的速度行走。關(guān)燈不需要花費(fèi)額外的時間，因?yàn)楫?dāng)他通過時就能將燈關(guān)掉。
編寫程序，計(jì)算在給定路燈設(shè)置，燈泡功率以及多端卡的起始位置的情況下關(guān)掉所有的燈需耗費(fèi)的最小能量。
【輸入】
輸入文件的第一行包含一個整數(shù)N，2≤N≤1000，表示該村莊路燈的數(shù)量。
第二行包含一個整數(shù)V，1≤V≤N，表示多瑞卡開始關(guān)燈的路燈號碼。
接下來的N行中，每行包含兩個用空格隔開的整數(shù)D和W，用來描述每盞燈的參數(shù)，其中0≤D≤1000，0≤W≤1000。D表示該路燈與村莊開始處的距離(用米為單位來表示)，W表示燈泡的功率，即在每秒鐘該燈泡所消耗的能量數(shù)。路燈是按順序給定的。
【輸出】
輸出文件的第一行即唯一的一行應(yīng)包含一個整數(shù)，即消耗能量之和的最小值。注意結(jié)果不超過1,000,000,000。
【樣例】
| POWER.IN | POWER.OUT |
4
3
2 2
5 8
6 1
8 7 | 56 |
【分析】
用c[i][j]表示關(guān)掉i到j(luò)的燈，剩下的燈的功率。
f[i][j][0]表示v左面關(guān)掉i，右面關(guān)掉j盞燈，最后停到左面。
f[i][j][1]表示v左面關(guān)掉i，右面關(guān)掉j盞燈，最后停到右面。
初始條件：
f[0,0,0]=f[1,0,0]=0
轉(zhuǎn)移方程：//對于所有的i和j，滿足0<i<=v-1，0<j<=n-v
f[0,I,0]=f[0,i-1,0]+c[v-i+1,v]*(d[v-i+1]-d[v-i]){從i-1走到i所耗功率}
f[1,I,0]=f[0,I,0]+c[v-I,v]*(d[v]-d[v-i]){ {從i走到v所耗功率}
f[1,0,j]=f[1,0,j-1]+c[v,v+j-1]*(d[v+j]-d[v+j-1])
f[0,0,j]=f[1,0,j]+c[v,v+j]*(d[v+j]-d[v])
f[0,I,j]=min{f[0,i-1,j]+(d[v-i+1]-d[v-i])*c[v-i+1,v+j]，f[1,i-1,j]+(d[v+j]-d[v-i])*c[v-i+1,v+j]}
f[1,I,j]=min{f[1,I,j-1]+(d[v+j]-d[v+j-1])*c[v-I,v+j-1]，f[0][I,j-1]+(d[v+j]-d[v-i])*c[v-I,v+j-1]}
最終結(jié)果： Result=min{f[0,v-1,n-v],f[1,v-1,n-v]}
1: #include <stdio.h>
2: #include <iostream>
3: #define maxn 1010
4: using namespace std;
5:
6: int c[maxn][maxn];
7: int sum[maxn][maxn];
8: int d[maxn],w[maxn];
9: int n,v;
10: int f[maxn][maxn][2];
11:
12: int main()
13: {
14: freopen("power.in","r",stdin);
15: freopen("power.out","w",stdout);
16:
17: scanf("%d%d",&n,&v);
18: for (int i=1;i<=n;++i) scanf("%d%d",&d[i],&w[i]);
19: for (int i=1;i<=n;++i)
20: for (int j=i;j<=n;++j)
21: sum[i][j]=sum[i][j-1]+w[j];
22: for (int i=1;i<=n;++i)
23: for (int j=i;j<=n;++j)
24: c[i][j]=sum[1][n]-sum[i][j];
25: memset(f,63,sizeof(f));
26: f[0][0][0]=f[0][0][1]=0; //0left 1right
27: for (int i=1;i<=v-1;++i)
28: {
29: f[i][0][0]=f[i-1][0][0]+c[v-i+1][v]*(d[v-i+1]-d[v-i]);
30: f[i][0][1]=f[i][0][0]+c[v-i][v]*(d[v]-d[v-i]);
31: }
32: for (int j=1;j<=n-v;++j)
33: {
34: f[0][j][1]=f[0][j-1][1]+c[v][v+j-1]*(d[v+j]-d[v+j-1]);
35: f[0][j][0]=f[0][j][1]+c[v][v+j]*(d[v+j]-d[v]);
36: }
37: for (int i=1;i<=v-1;++i)
38: for (int j=1;j<=n-v;++j)
39: {
40: f[i][j][0]=min(f[i-1][j][0]+c[v-i+1][v+j]*(d[v-i+1]-d[v-i]),f[i-1][j][1]+c[v-i+1][v+j]*(d[v+j]-d[v-i]));
41: f[i][j][1]=min(f[i][j-1][1]+c[v-i][v+j-1]*(d[v+j]-d[v+j-1]),f[i][j-1][0]+c[v-i][v+j-1]*(d[v+j]-d[v-i]));
42: }
43: printf("%d\n",min(f[v-1][n-v][1],f[v-1][n-v][0]));
44: return 0;
45: }
46:
47: