中文国产成人精品久久不卡,久久久久久久综合日本亚洲 ,久久99国产精品久久99小说

注目了阿�Q�！�Q�～～～

Sephiroth Lee — Sat, 11 Sep 2010 04:09:00 GMT

更换blog �Q�因为特�D�原�? http://www.cnblogs.com/sephirothlee/

Sephiroth Lee 2010-09-11 12:09 发表评论

WIN7体验

Sephiroth Lee — Tue, 07 Sep 2010 02:09:00 GMT

今天用差不多半天的时间把WIN7装好了，太篏��Z��?/font>

昑֍��q�是太垃�䏀��?�{�放假去��N��怸�个回来！�Q�……（有点不好的说�Q?/font>

1G的内存，占用量一直在54%左右。确实很吃硬件�?/font>

Sephiroth Lee 2010-09-07 10:09 发表评论

“长沙一中学�?amp;rdquo;-day4

Sephiroth Lee — Fri, 03 Sep 2010 23:56:00 GMT

今天上午是搜索�?/p>

最��乘法次�?/li>
彩票问题
黑白��游�?/li>
pku1729
多处理机调度问题
��盘
最短编号序�?/li>
��d��安排
数字游戏(c&m)
埃及分数
antiprime

下午是数学的一些东�ѝ�?/p>

�W�二�c�string�?/li>
卡特兰数
polya原理
整数分解
极值问�?/li>
Kathy函数
错排问题
求Fibonacci数列
毛毛�?/li>
一序列
圆桌吃饭
01串问�?/li>
��术表达式的计算

Sephiroth Lee 2010-09-04 07:56 发表评论

旉��奔流

Sephiroth Lee — Thu, 02 Sep 2010 13:54:00 GMT

旉��

奔流�?/p>

本来是EVA的一个同人小说、某�|�友的ID。现在突然有�q�种感觉了�?/p>

五天的集训，现在�W�三天就要结束了�Q�明天就�?受��?/p>

4��P��5��P��6号回东区。然后猛补文化课�Q�再有一个月�Q�就开始最后的准备了�?/p>

11�?1日，上战场的日子�?/p>

��Z��宝贝儿，��Z��我自己�?/p>

Sephiroth Lee 2010-09-02 21:54 发表评论

“长沙一中学�?amp;rdquo;-day3

Sephiroth Lee — Thu, 02 Sep 2010 12:58:00 GMT

上午讲的动态规划的优化。有很多�l�典的例题�?/p>

宝物�{��?/li>
农田个数
花店��q��布置
乘�R路线
叠放��子
演唱�l?/li>
divide
��d��?/li>
走道铺砖问题
股票问题
火�R��?/li>
杀蚂蚁
��C��华尔�?/li>

下午开始了搜烦�Q�有�Ҏ��?/p>

走迷宫问�?/li>
订货�?/li>
计算机网�l�连�?/li>
N皇后
Betsy’s tour

晚上好好休息�?/p>

Sephiroth Lee 2010-09-02 20:58 发表评论

树归-珠宝

Sephiroth Lee — Thu, 02 Sep 2010 12:40:00 GMT

【描�q��?

�l�一��n个结点的树，�l�每个点安排一个正整数�~�号�Q��得相�ȝ��h��不同的编��P��~�号的��d��量��?br>【输入�?br>�W�一行：n(n<=50,000)
以下n-1行，每行两个数u,v(1<=u,v<=n)�Q�表�C�u 和v有一条边
【输出�?br>仅一行，为最��编号和
【样例输入�?br>8
1 2
1 3
1 4
1 5
5 6
5 7
5 8
【样例输出�?br>11

【分析�?

f[i][j]表示i�q�个�Ҏ��j�q�个数所能到辄��最��d��{��控制j的范围到30肯定�q��?/p>

  1: #include 
  2: #include 
  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] 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 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] 62:             ans=f[1][i];
 63:     printf("%d\n",ans);
 64:     return 0;
 65: }
 66: 


Sephiroth Lee 2010-09-02 20:40 发表评论

动态规�?皇宫看守

Sephiroth Lee — Thu, 02 Sep 2010 11:58:00 GMT

【问题描�q��?/p>

太��^王世子事件后�Q�陆��凤成了皇上特聘的�M前一品侍卫�?/p>

皇宫以午门�ؓ��L��Q�直到后宫嫔妃们的寝宫，呈一��|��的�Ş�Ӟ��某些宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有�h全天候看守，在不同的宫殿安排看守所需的费用不同�?/p>

可是陆小凤手上的�l�费不��Q�无论如何也没法在每个宫�D�K��安置留守侍卫�?/p>

帮助陆小凤布�|�侍卫，在看守全部宫�D�的前提下，使得��p��的经�Ҏ��?/p>

【数据输入�?/p>

输入数据由文件名为INPUT.TXT的文本文件提供。输入文件中数据表示一��|��Q�描�q�如下：

�W?�?n�Q�表�C�树中结点的数目�?/p>

�W?行至�W�n+1行，每行描述每个宫殿�l�点信息�Q�依�ơ�ؓ�Q�该宫殿�l�点标号i�Q?

对于一个n�Q? < n <= 1500�Q�个�l�点的树�Q�结�Ҏ��号在1到n之间�Q�且标号不重复�?/p>

【数据输出�?/p>

输出到OUTPUT.TXT文�g中。输出文件仅包含一个数�Q��ؓ所求的最��的�l�费�?/p>

输入数据�C�Z�� 　输出数据�C�Z��

【分析�?/p>

分别用f[i][0]表示i�Ҏ��看守�Q�f[i][1]表示i点不攄��守i点被儿子监视�Q�f[i][2]表示i点不攄��守i点被父节点监视三个情况下的最��费用�?/p>

f[i][0]=所有子节点t的f[t][0],f[t][1],f[t][2]中最��的一个的�?k[i]

f[i][1]=某个子节�Ҏ��看守+其他节点的f[t][0],f[t][1]中最��的一个的�?/p>

f[i][2]=所有子节点的f[t][1]的合

  1: #include 
  2: #include 
  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] 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: 


Sephiroth Lee 2010-09-02 19:58 发表评论

Sephiroth Lee — Thu, 02 Sep 2010 11:15:00 GMT

题目见ural1039

  1: #include 
  2: #include 
  3: #include 
  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.roreturn -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 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: 


Sephiroth Lee 2010-09-02 19:15 发表评论

��d��安排

Sephiroth Lee — Thu, 02 Sep 2010 10:39:00 GMT

【描�q��?

N个�Q务排成一个序列在一台机器上�{�待完成�Q�顺序不得改变）�Q�这N个�Q务被分成若干批，每批包含盔R��的若�q��Q务。从时刻0开始，�q�些��d��被分批加工，�W�i个�Q务单独完成所需的时间是Ti。在每批��d��开始前�Q�机器需要启动时间S�Q�而完成这批�Q务所需的时间是各个��d��需要时间的��d��Q�同一批�Q务将在同一时刻完成�Q�。每个�Q务的费用是它的完成时��M��以一个费用系数Fi。请��定一个分�l�方案，使得总费用最��?例如�Q�S=1�Q�T={1,3,4,2,1}�Q�F={3,2,3,3,4}。如果分�l�方案是{1,2}、{3}、{4,5}�Q�则完成旉��分别为{5,5,10,14,14}�Q�费用C{15,10,30,42,56}�Q�总费用就�?53�?

【输入�?/p>

�W�一行是N(1<=N<=5000)�?�W�二行是S(0<=S<=50)�?下面N行每行有一�Ҏ��Q�分别�ؓTi和Fi�Q�均��Z��大于100的正整数�Q�表�C�第i个�Q务单独完成所需的时间是Ti及其费用�p�L��Fi�?

【输出�?

一个数�Q�最��的总费用�?br>【样例�?/p>

BATCH.IN	BATCH.OUT
5 1 1 3 3 2 4 3 2 3 1 4	153

【分析�?/p>

dp[i]�Q�完成工�?到工作I的费�?因增加S从I到N增加的费用的��d��的最��费用�?/p>

dp[i]=min{dp[k-1]+s*(f[n]-f[k-1])+t[i]*(f[i]-f[k-1])}

  1: #include 
  2: #include 
  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 30:         }
 31:     printf("%d\n",dp[n]);
 32:     return 0;
 33: }
 34: 


Sephiroth Lee 2010-09-02 18:39 发表评论

动态规�?关灯

Sephiroth Lee — Thu, 02 Sep 2010 03:54:00 GMT

【描�q��?

多瑞卡得��C��一份有��而高薪的工作。每天早晨他必须��x��他所在村庄的街灯。所有的街灯都被讄��在一条直路的同一侧�?br>多瑞卡每天到早晨5炚w��都按时�v床，然后他开始关灯。开始时�Q�他站在某一盏�\灯的旁边�?br>每盏灯都有一个给定功率的�늁�泡，因�ؓ多端卡有着自觉的节能意识，他希望在耗电能��L��最��的情况下将所有的灯关掉�?br>多端卡因为太累了�Q�所以只能以1m/s的速度行走。关灯不需要花贚w��外的旉��Q�因为当他通过时就能将灯关掉�?br>�~�写�E�序�Q�计��在�l�定路灯讄��Q�灯泡功率以及多端卡的�v始位�|�的情况下关掉所有的灯需耗费的最��能量�?br>【输入�?br>输入文�g的第一行包含一个整数N�Q?≤N�?000�Q�表�C��村庄路灯的数量�?br>�W�二行包含一个整数V�Q?≤V≤N�Q�表�C�多瑞卡开始关灯的路灯��L��?br>接下来的N行中�Q�每行包含两个用�I�格隔开的整数D和W�Q�用来描�q�每盏灯的参敎ͼ�其中0≤D�?000�Q?≤W�?000。D表示该�\灯与村庄开始处的距��?用米为单位来表示)�Q�W表示灯��的功率，卛_��每秒钟该灯��所消耗的能量数。�\灯是按顺序给定的�?br>【输出�?br>输出文�g的第一行即唯一的一行应包含一个整敎ͼ��x��耗能量之和的最��倹{��注意结果不��过1,000,000,000�?br>【样例�?/p>

POWER.IN	POWER.OUT
4 3 2 2 5 8 6 1 8 7	56

【分析�?/p>

用c[i][j]表示��x��i到j的灯�Q?u>剩下的灯的功率�?/p>

f[i][j][0]表示v左面��x��i�Q�右面关掉j盏灯�Q�最后停到左面�?/p>

f[i][j][1]表示v左面��x��i�Q�右面关掉j盏灯�Q�最后停到右面�?/p>

初始条�g�Q?/p>

f[0,0,0]=f[1,0,0]=0

转移方程�Q?/对于所有的i和j�Q�满��?

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]�Q�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]�Q�f[0][I,j-1]+(d[v+j]-d[v-i])*c[v-I,v+j-1]}

最�l�结果： Result=min{f[0,v-1,n-v],f[1,v-1,n-v]}

  1: #include 
  2: #include 
  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:

Sephiroth Lee 2010-09-02 11:54 发表评论

中文国产成人精品久久不卡,久久久久久久综合日本亚洲 ,久久99国产精品久久99小说

注目了阿�Q�！�Q�～～～

WIN7体验

“长沙一中学�?amp;rdquo;-day4

旉���奔流

“长沙一中学�?amp;rdquo;-day3

树归-珠宝

动态规�?皇宫看守

��d��安排

动态规�?关灯

旉��奔流