今天用差不多半天的时间把WIN7装好了，太累人了。
显卡还是太垃圾…… 等放假去宾馆卸一个回来！！……（有点不好的说）
1G的内存，占用量一直在54%左右。确实很吃硬件。
时间
奔流。
本来是EVA的一个同人小说、某网友的ID。现在突然有这种感觉了。
五天的集训，现在第三天就要结束了，明天就是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这个数所能到达的最小总值。控制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: