Sephiroth's boring days!!!

[置頂]注目了阿！！！～～～

posted @ 2010-09-11 12:09 Sephiroth Lee 閱讀(181) | 評論 (0) | 編輯 收藏

注目了阿！！！～～～

posted @ 2010-09-11 12:09 Sephiroth Lee 閱讀(181) | 評論 (0) | 編輯 收藏

WIN7體驗

今天用差不多半天的時間把WIN7裝好了，太累人了。

顯卡還是太垃圾…… 等放假去賓館卸一個回來！！……（有點不好的說）

1G的內(nèi)存，占用量一直在54%左右。確實很吃硬件。

posted @ 2010-09-07 10:09 Sephiroth Lee 閱讀(293) | 評論 (0) | 編輯 收藏

“長沙一中學(xué)習(xí)”-day4

今天上午是搜索。

1. 最少乘法次數(shù)
2. 彩票問題
3. 黑白棋游戲
4. pku1729
5. 多處理機調(diào)度問題
6. 魔盤
7. 最短編號序列
8. 任務(wù)安排
9. 數(shù)字游戲(c&m)
10. 埃及分數(shù)
11. antiprime

下午是數(shù)學(xué)的一些東西。

1. 第二類string數(shù)
2. 卡特蘭數(shù)
3. polya原理
4. 整數(shù)分解
5. 極值問題
6. Kathy函數(shù)
7. 錯排問題
8. 求Fibonacci數(shù)列
9. 毛毛蟲
10. 一序列
11. 圓桌吃飯
12. 01串問題
13. 算術(shù)表達式的計算

posted @ 2010-09-04 07:56 Sephiroth Lee 閱讀(492) | 評論 (1) | 編輯 收藏

時間奔流

時間

奔流。

本來是EVA的一個同人小說、某網(wǎng)友的ID。現(xiàn)在突然有這種感覺了。

五天的集訓(xùn)，現(xiàn)在第三天就要結(jié)束了，明天就是3號。

4號，5號，6號回東區(qū)。然后猛補文化課，再有一個月，就開始最后的準備了。

11月21日，上戰(zhàn)場的日子。

為了寶貝兒，為了我自己。

posted @ 2010-09-02 21:54 Sephiroth Lee 閱讀(554) | 評論 (2) | 編輯 收藏

“長沙一中學(xué)習(xí)”-day3

上午講的動態(tài)規(guī)劃的優(yōu)化。有很多經(jīng)典的例題。

1. 寶物篩選
2. 農(nóng)田個數(shù)
3. 花店櫥窗布置
4. 乘車路線
5. 疊放箱子
6. 演唱組
7. divide
8. 添加號
9. 走道鋪磚問題
10. 股票問題
11. 火車票
12. 殺螞蟻
13. 瑰麗華爾茲

下午開始了搜索，有點暈。

1. 走迷宮問題
2. 訂貨單
3. 計算機網(wǎng)絡(luò)連接
4. N皇后
5. Betsy’s tour

晚上好好休息。

posted @ 2010-09-02 20:58 Sephiroth Lee 閱讀(296) | 評論 (0) | 編輯 收藏

樹歸-珠寶

【描述】

給一棵n個結(jié)點的樹，給每個點安排一個正整數(shù)編號，使得相鄰點具有不同的編號，編號的總和盡量小。
【輸入】
第一行：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這個點標j這個數(shù)所能到達的最小總值。控制j的范圍到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: 

posted @ 2010-09-02 20:40 Sephiroth Lee 閱讀(350) | 評論 (0) | 編輯 收藏

動態(tài)規(guī)劃-皇宮看守

【問題描述】

太平王世子事件后，陸小鳳成了皇上特聘的御前一品侍衛(wèi)。

皇宮以午門為起點，直到后宮嬪妃們的寢宮，呈一棵樹的形狀；某些宮殿間可以互相望見。大內(nèi)保衛(wèi)森嚴，三步一崗，五步一哨，每個宮殿都要有人全天候看守，在不同的宮殿安排看守所需的費用不同。

可是陸小鳳手上的經(jīng)費不足，無論如何也沒法在每個宮殿都安置留守侍衛(wèi)。

幫助陸小鳳布置侍衛(wèi)，在看守全部宮殿的前提下，使得花費的經(jīng)費最少。

【數(shù)據(jù)輸入】

輸入數(shù)據(jù)由文件名為INPUT.TXT的文本文件提供。輸入文件中數(shù)據(jù)表示一棵樹，描述如下：

第1行 n，表示樹中結(jié)點的數(shù)目。

第2行至第n+1行，每行描述每個宮殿結(jié)點信息，依次為：該宮殿結(jié)點標號i（0<i<=n），在該宮殿安置侍衛(wèi)所需的經(jīng)費k，該邊的兒子數(shù)m，接下來m個數(shù)，分別是這個節(jié)點的m個兒子的標號r1，r2，...，rm。

對于一個n（0 < n <= 1500）個結(jié)點的樹，結(jié)點標號在1到n之間，且標號不重復(fù)。

【數(shù)據(jù)輸出】

輸出到OUTPUT.TXT文件中。輸出文件僅包含一個數(shù)，為所求的最少的經(jīng)費。

輸入數(shù)據(jù)示例 　輸出數(shù)據(jù)示例

      25

【分析】

分別用f[i][0]表示i點放看守，f[i][1]表示i點不放看守i點被兒子監(jiān)視，f[i][2]表示i點不放看守i點被父節(jié)點監(jiān)視三個情況下的最小費用。

f[i][0]=所有子節(jié)點t的f[t][0],f[t][1],f[t][2]中最小的一個的合+k[i]

f[i][1]=某個子節(jié)點放看守+其他節(jié)點的f[t][0],f[t][1]中最小的一個的合

f[i][2]=所有子節(jié)點的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: 

posted @ 2010-09-02 19:58 Sephiroth Lee 閱讀(1065) | 評論 (1) | 編輯 收藏

聚會的快樂

題目見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: 

posted @ 2010-09-02 19:15 Sephiroth Lee 閱讀(446) | 評論 (0) | 編輯 收藏

任務(wù)安排

【描述】

N個任務(wù)排成一個序列在一臺機器上等待完成（順序不得改變），這N個任務(wù)被分成若干批，每批包含相鄰的若干任務(wù)。從時刻0開始，這些任務(wù)被分批加工，第i個任務(wù)單獨完成所需的時間是Ti。在每批任務(wù)開始前，機器需要啟動時間S，而完成這批任務(wù)所需的時間是各個任務(wù)需要時間的總和（同一批任務(wù)將在同一時刻完成）。每個任務(wù)的費用是它的完成時刻乘以一個費用系數(shù)Fi。請確定一個分組方案，使得總費用最小。 例如：S=1；T={1,3,4,2,1}；F={3,2,3,3,4}。如果分組方案是{1,2}、{3}、{4,5}，則完成時間分別為{5,5,10,14,14}，費用C{15,10,30,42,56}，總費用就是153。

【輸入】

第一行是N(1<=N<=5000)。 第二行是S(0<=S<=50)。 下面N行每行有一對數(shù)，分別為Ti和Fi，均為不大于100的正整數(shù)，表示第i個任務(wù)單獨完成所需的時間是Ti及其費用系數(shù)Fi。

【輸出】

一個數(shù)，最小的總費用。
【樣例】

【分析】

dp[i]：完成工作1到工作I的費用+因增加S從I到N增加的費用的總和的最小費用。

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: 

posted @ 2010-09-02 18:39 Sephiroth Lee 閱讀(297) | 評論 (0) | 編輯 收藏

動態(tài)規(guī)劃-關(guān)燈

【描述】

多瑞卡得到了一份有趣而高薪的工作。每天早晨他必須關(guān)掉他所在村莊的街燈。所有的街燈都被設(shè)置在一條直路的同一側(cè)。
多瑞卡每天到早晨5點鐘都按時起床，然后他開始關(guān)燈。開始時，他站在某一盞路燈的旁邊。
每盞燈都有一個給定功率的電燈泡，因為多端卡有著自覺的節(jié)能意識，他希望在耗電能總數(shù)最少的情況下將所有的燈關(guān)掉。
多端卡因為太累了，所以只能以1m/s的速度行走。關(guān)燈不需要花費額外的時間，因為當(dāng)他通過時就能將燈關(guān)掉。
編寫程序，計算在給定路燈設(shè)置，燈泡功率以及多端卡的起始位置的情況下關(guān)掉所有的燈需耗費的最小能量。
【輸入】
輸入文件的第一行包含一個整數(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。
【樣例】

【分析】

用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: 

posted @ 2010-09-02 11:54 Sephiroth Lee 閱讀(470) | 評論 (0) | 編輯 收藏