今天用差不多半天的時間把WIN7裝好了，太累人了。
顯卡還是太垃圾…… 等放假去賓館卸一個回來?。 ㄓ悬c不好的說）
1G的內存，占用量一直在54%左右。確實很吃硬件。
時間
奔流。
本來是EVA的一個同人小說、某網友的ID?，F在突然有這種感覺了。
五天的集訓，現在第三天就要結束了，明天就是3號。
4號，5號，6號回東區。然后猛補文化課，再有一個月，就開始最后的準備了。
11月21日，上戰場的日子。
為了寶貝兒，為了我自己。
【描述】
給一棵n個結點的樹，給每個點安排一個正整數編號，使得相鄰點具有不同的編號，編號的總和盡量小。
【輸入】
第一行：n(n<=50,000)
以下n-1行，每行兩個數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這個數所能到達的最小總值?？刂苆的范圍到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:
【問題描述】
太平王世子事件后，陸小鳳成了皇上特聘的御前一品侍衛。
皇宮以午門為起點，直到后宮嬪妃們的寢宮，呈一棵樹的形狀；某些宮殿間可以互相望見。大內保衛森嚴，三步一崗，五步一哨，每個宮殿都要有人全天候看守，在不同的宮殿安排看守所需的費用不同。
可是陸小鳳手上的經費不足，無論如何也沒法在每個宮殿都安置留守侍衛。
幫助陸小鳳布置侍衛，在看守全部宮殿的前提下，使得花費的經費最少。
【數據輸入】
輸入數據由文件名為INPUT.TXT的文本文件提供。輸入文件中數據表示一棵樹，描述如下：
第1行 n，表示樹中結點的數目。
第2行至第n+1行，每行描述每個宮殿結點信息，依次為：該宮殿結點標號i（0<i<=n），在該宮殿安置侍衛所需的經費k，該邊的兒子數m，接下來m個數，分別是這個節點的m個兒子的標號r1，r2，...，rm。
對于一個n（0 < n <= 1500）個結點的樹，結點標號在1到n之間，且標號不重復。
【數據輸出】
輸出到OUTPUT.TXT文件中。輸出文件僅包含一個數，為所求的最少的經費。
輸入數據示例 輸出數據示例
25
【分析】
分別用f[i][0]表示i點放看守，f[i][1]表示i點不放看守i點被兒子監視，f[i][2]表示i點不放看守i點被父節點監視三個情況下的最小費用。
f[i][0]=所有子節點t的f[t][0],f[t][1],f[t][2]中最小的一個的合+k[i]
f[i][1]=某個子節點放看守+其他節點的f[t][0],f[t][1]中最小的一個的合
f[i][2]=所有子節點的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個任務排成一個序列在一臺機器上等待完成（順序不得改變），這N個任務被分成若干批，每批包含相鄰的若干任務。從時刻0開始，這些任務被分批加工，第i個任務單獨完成所需的時間是Ti。在每批任務開始前，機器需要啟動時間S，而完成這批任務所需的時間是各個任務需要時間的總和（同一批任務將在同一時刻完成）。每個任務的費用是它的完成時刻乘以一個費用系數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行每行有一對數，分別為Ti和Fi，均為不大于100的正整數，表示第i個任務單獨完成所需的時間是Ti及其費用系數Fi。
【輸出】
一個數，最小的總費用。
【樣例】
| BATCH.IN | BATCH.OUT |
5
1
1 3
3 2
4 3
2 3
1 4 | 153 |
【分析】
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:
【描述】
多瑞卡得到了一份有趣而高薪的工作。每天早晨他必須關掉他所在村莊的街燈。所有的街燈都被設置在一條直路的同一側。
多瑞卡每天到早晨5點鐘都按時起床，然后他開始關燈。開始時，他站在某一盞路燈的旁邊。
每盞燈都有一個給定功率的電燈泡，因為多端卡有著自覺的節能意識，他希望在耗電能總數最少的情況下將所有的燈關掉。
多端卡因為太累了，所以只能以1m/s的速度行走。關燈不需要花費額外的時間，因為當他通過時就能將燈關掉。
編寫程序，計算在給定路燈設置，燈泡功率以及多端卡的起始位置的情況下關掉所有的燈需耗費的最小能量。
【輸入】
輸入文件的第一行包含一個整數N，2≤N≤1000，表示該村莊路燈的數量。
第二行包含一個整數V，1≤V≤N，表示多瑞卡開始關燈的路燈號碼。
接下來的N行中，每行包含兩個用空格隔開的整數D和W，用來描述每盞燈的參數，其中0≤D≤1000，0≤W≤1000。D表示該路燈與村莊開始處的距離(用米為單位來表示)，W表示燈泡的功率，即在每秒鐘該燈泡所消耗的能量數。路燈是按順序給定的。
【輸出】
輸出文件的第一行即唯一的一行應包含一個整數，即消耗能量之和的最小值。注意結果不超過1,000,000,000。
【樣例】
| POWER.IN | POWER.OUT |
4
3
2 2
5 8
6 1
8 7 | 56 |
【分析】
用c[i][j]表示關掉i到j的燈，剩下的燈的功率。
f[i][j][0]表示v左面關掉i，右面關掉j盞燈，最后停到左面。
f[i][j][1]表示v左面關掉i，右面關掉j盞燈，最后停到右面。
初始條件：
f[0,0,0]=f[1,0,0]=0
轉移方程：//對于所有的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]}
最終結果： 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: