#
恩，日本漫画啊游戏啊经常出现觉悟这个词，再就是觉醒。我突然也想说：“我要有所觉悟了！”
摆弄了几天弧光之源2，虽然故事很吸引人但是今天突然感到，自己在浪费时间。就像老师经常说到的，“等报送了随便玩”。对现在就是这个感觉，等报送了laptop，Xbox，ps3，Wii，NDSi，PSP我都可以随便玩了，但是现在不行。
借用弧光之源2火之魔女的话来说：“我还是学生，游戏停止。”
不知道怎么回事，chrome产生bug了。安装插件的时候就会提示我什么什么文件夹无法创建。
用开发者模式可以载入扩展，可恶，chrome你怎么了？？
重新安装了一遍chrome stable版，然后按照网上的说法改了一下temp和tem变量的路径，解决~
哦哦~ 又能装扩展了~
有依赖的背包，正好刚刚学到。
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:
上周noip吧进行的编程挑战赛。
相关内容见“【传送门】百度NOIP吧编程挑战赛相关帖子”
第三题是一道有依赖的背包问题。今天dev问到了，于是又回忆了一下。徐持衡大牛的集训队论文中关于泛化物品的并还是不太懂。但是对这种背包有点了自己的感悟。
这道题目对我来说有两个启发点：
- 对多儿子的处理，用的是nlogn的预处理。
- 树形的背包。
1.多儿子的处理
用结构体记录关系，a[i].root是第i个关系的父节点，a[i].num是第i个关系的子节点。将数组按root排序。然后用t[i]记录i这个点的儿子在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个点的子节点在a中的位置就是从t[i]到t[i+1]-1。
免去了链表的繁琐，效率还相当高。
2.树形的背包
主要思想就是对于i的节点s，f[s]强制赋值为f[i]，然后强制加入w[s],对s进行处理，再更新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: }
相当棒的解决问题。
3.一些习题
- CTSC98-选课
昨天晚上抽风了不想睡，俯卧撑啊仰卧起坐啊折腾了50就11点了o(╯□╰)o。然后就听见外面“哗……”。心里暗爽啊~哦也，明天不用跑操了！~
早上醒来5点08。刚醒来的时候以为4点多，一看表惊了一下。这天气也够反常的了，夏天没怎么下雨，现在开始下大雨了。还没有风，就那么几片云在头顶上来回下。
计划在9月11号放假之前买入一套ACU，大概在600~800的价格，要好好的钻研一下。
今天又是一天的课……只有一节奥赛，坚持坚持！
在我的电脑上表现比IE还差劲！
更换Safari。
还是chrome好啊……我用的是世界之窗版的。
立姐者，老班也。真名我就不提了，认识我的人应该都知道。不过有一点必须说明——＂立姐＂是男的。
１.这个印的不清楚啊，你可得看清楚了。（发现了……我们都是超能力，不清楚的能看清楚喽。）
２.从第一年一月一号到第二年二月一号一年的时间。（恩恩，才知道月份也要加一。）
图一张～
一鸡骨新形象……
长发，ms身高也长了……忘记他老爸给他争取多长时间了……
去吃午饭~ 下午再写。
98自己也说过，bleach的风格就是绝对的帅。从雨龙的出现到一护的西装卍解，98用角色的帅气征服了很多人。
bleach给我的感受，是永不放弃，是信任朋友，是勇往直前的勇气。不管对手多么强大，把他打败就好了。
尽管看漫画在很多人眼里是不务正业，但是我认为bleach给我的一些启示，是很有用的。一护那种就算被打的无法动弹也要拼命拿起刀的精神，那种强大的意志力，是我永远效仿并努力做到的东西。
虽然有98提供的官方外挂，但是我还是要说：“一护，加油！”
1.应用的时间
在自己搭建了自己的blog之前，就常住这个blog了……
2.原来的Blogs
原来用的Baidu，blogbus，csdn全部弃用，不过说来也没有那个用的超过半年的。
blogger，MySpace的博客，大家都懂的，麻烦死了。干脆不用了。
3.这个博客的用途
用于记录本人的心情和感悟。
发现的有趣的东西，有用的东西。
OI之路上的经历。
4.你的blog里的代码是怎么弄的啊？
我是用live writer些blog的，应用了一个插件“WLWSourceCodePluginSetup.msi”。大家可以在Internet上搜索到。
5.为什么你发表的都是“随笔”而没有“文章”啊？
这个是writer和cppblog的web服务问题（Google上这么说的）。所以通过writer发表的都是随笔而没有文章。那我索性就都弄成随笔了。