覺悟-游戲停止

恩，日本漫畫啊游戲啊經(jīng)常出現(xiàn)覺悟這個(gè)詞，再就是覺醒。我突然也想說：“我要有所覺悟了！”

擺弄了幾天弧光之源2，雖然故事很吸引人但是今天突然感到，自己在浪費(fèi)時(shí)間。就像老師經(jīng)常說到的，“等報(bào)送了隨便玩”。對(duì)現(xiàn)在就是這個(gè)感覺，等報(bào)送了laptop，Xbox，ps3，Wii，NDSi，PSP我都可以隨便玩了，但是現(xiàn)在不行。

借用弧光之源2火之魔女的話來說：“我還是學(xué)生，游戲停止。”

posted @ 2010-08-28 08:06 Sephiroth Lee 閱讀(159) | 評(píng)論 (0) | 編輯收藏

郁悶……我的chrome不能裝插件

~~不知道怎么回事，chrome產(chǎn)生bug了。安裝插件的時(shí)候就會(huì)提示我什么什么文件夾無(wú)法創(chuàng)建。~~

~~用開發(fā)者模式可以載入擴(kuò)展，可惡，chrome你怎么了？？~~

重新安裝了一遍chrome stable版，然后按照網(wǎng)上的說法改了一下temp和tem變量的路徑，解決~

哦哦~ 又能裝擴(kuò)展了~

posted @ 2010-08-27 19:49 Sephiroth Lee 閱讀(656) | 評(píng)論 (1) | 編輯收藏

題目&知識(shí)分類

1.動(dòng)態(tài)規(guī)劃

2.貪心

貪心-買彩票

3.數(shù)學(xué)問題

數(shù)學(xué)問題-Black and White

posted @ 2010-08-27 18:08 Sephiroth Lee 閱讀(155) | 評(píng)論 (0) | 編輯收藏

CTSC98-選課

有依賴的背包，正好剛剛學(xué)到。

  1: #include <stdio.h>
  2: #include <stdlib.h>
  3: #define maxn 400
  4: 
  5: int f[maxn][maxn];
  6: int t[maxn];
  7: struct ss
  8: {
  9:     int root,num;
 10: } a[maxn];
 11: int n,m;
 12: int w[maxn];
 13: 
 14: int cmp(const void*a,const void*b)
 15: {
 16:     ss c=*(ss*)a,d=*(ss*)b;
 17:     if (c.root<d.root) return -1;
 18:     if (c.root>d.root) return 1;
 19:     return 0;
 20: }
 21: 
 22: void dp(int x)
 23: {
 24:     for (int i=t[x];i<t[x+1];++i)
 25:     {
 26:         int k=a[i].num;
 27:         for (int j=0;j<=m;++j) f[k][j]=f[x][j]+w[k];
 28:         dp(k);
 29:         for (int j=1;j<=m;++j)
 30:             if (f[k][j-1]>f[x][j])
 31:                 f[x][j]=f[k][j-1];
 32:     }
 33: }
 34: 
 35: int main()
 36: {
 37:     scanf("%d%d",&n,&m);
 38:     for (int i=1;i<=n;++i)
 39:     {
 40:         scanf("%d%d",&a[i].root,&w[i]);
 41:         a[i].num=i;
 42:     }
 43:     a[0].root=-1;
 44:     qsort(a,n+1,sizeof(ss),cmp);
 45:     for (int i=1;i<=n;++i)
 46:         if (!t[a[i].root])
 47:             t[a[i].root]=i;
 48:     t[n+1]=n+1;
 49:     for (int i=n;i>=0;--i)
 50:         if (!t[i])
 51:             t[i]=t[i+1];
 52:     dp(0);
 53:     printf("%d\n",f[0][m]);
 54:     return 0;
 55: }
 56:

posted @ 2010-08-27 18:05 Sephiroth Lee 閱讀(438) | 評(píng)論 (0) | 編輯收藏

樹形依賴背包——百度NOIP吧編程挑戰(zhàn)賽"charge"

上周noip吧進(jìn)行的編程挑戰(zhàn)賽。

相關(guān)內(nèi)容見“【傳送門】百度NOIP吧編程挑戰(zhàn)賽相關(guān)帖子”

第三題是一道有依賴的背包問題。今天dev問到了，于是又回憶了一下。徐持衡大牛的集訓(xùn)隊(duì)論文中關(guān)于泛化物品的并還是不太懂。但是對(duì)這種背包有點(diǎn)了自己的感悟。

這道題目對(duì)我來說有兩個(gè)啟發(fā)點(diǎn)：

對(duì)多兒子的處理，用的是nlogn的預(yù)處理。
樹形的背包。

1.多兒子的處理

用結(jié)構(gòu)體記錄關(guān)系，a[i].root是第i個(gè)關(guān)系的父節(jié)點(diǎn)，a[i].num是第i個(gè)關(guān)系的子節(jié)點(diǎn)。將數(shù)組按root排序。然后用t[i]記錄i這個(gè)點(diǎn)的兒子在a中的起始位置。

  1: struct ss
  2: {
  3:     int root,num;
  4: } a[maxn];
  5: int t[maxn];
  6: 
  7: void init()
  8: {
  9:     qsort(a,n,sizeof(ss),cmp);
 10:     for (int i=1;i<=n;++i)
 11:         if (!t[a[i].root])
 12:             t[a[i].root]=i;
 13:     t[n+1]=n+1;
 14:     for (int i=n;i>0;--i)
 15:         if (!t[i])
 16:             t[i]=t[i+1];
 17: }
 18:

這樣第i個(gè)點(diǎn)的子節(jié)點(diǎn)在a中的位置就是從t[i]到t[i+1]-1。

免去了鏈表的繁瑣，效率還相當(dāng)高。

2.樹形的背包

主要思想就是對(duì)于i的節(jié)點(diǎn)s，f[s]強(qiáng)制賦值為f[i]，然后強(qiáng)制加入w[s],對(duì)s進(jìn)行處理，再更新f[i]。

  1: void dp(int x)
  2: {
  3:     for (int i=t[x];i<t[x+1];++i)
  4:     {
  5:         int k=a[i].num;
  6:         for (int j=0;j<=V;++j) f[k][j]=f[x][j]+w[k];
  7:         dp(k);
  8:         for (int j=v[k];j<=V;++j)
  9:             if (f[k][j-v[k]]>f[x][j])
 10:                 f[x][j]=f[k][j-v[k]];
 11:     }
 12: }