Posted on 五月 13th, 2008.
具体题解看这里:http://www.briefdream.com/sgu-116/
这道题很囧的一点是,我一直不知道背包的一维写法…其实就是f[i]=min(f[i-a[j]])+1,然后就ok了…囧死了,因为这个MLE了…改后AC.
{ SGU 116; Index of super-prime - sqybi’s code - DP(package)}//for my winstyprogram sgu116_sqybi; const nn = 10000; inf = 1000000;
var n, i, j, lp, lsp, outl: longint; sp, p, outArr: array[1..nn]of longint; pf: array[1..nn]of boolean; d, path: array[0..nn]of longint;
procedure qsort(l, r: longint); var i, j, d, t: longint; begin if […]
Read Full Post |
Make a Comment ( None so far )
Posted on 五月 10th, 2008.
很经典的DP了.f[i, j]表示前i束花放在前j个花瓶里,其中第i束花必须放在第j个花瓶.转移方程很显然.似乎没有第i束花必须放在第j个花瓶的条件,转移复杂度会低…反正随便写写就可以AC啦…
{ SGU 104; Little shop of flowers - sqybi’s code - DP}//for my winstyprogram sgu104_sqybi; const nn = 100;
var n, m, i, j, p, min: longint; a, d, path: array[1..nn, 1..nn]of longint;
procedure f(x, y: longint); var i: longint; begin if x = y then begin d[x, y] := 0; for […]
Read Full Post |
Make a Comment ( 2 so far )
Posted on 四月 22nd, 2008.
庆祝一下,这道题AC之后得到了宝贵的0.4分,于是以4.4分的成绩拿到了1000名…整1000名啊…一个不差…截图就不发了…
这道题是一道挺弱智的DP,和冰峰文有些类似,比那个还要简单.dset[l, r]表示从l到r这一段是不是一个set,而dlist[l, r]表示l到r是不是list.然后转移的时候考虑全就可以.其中判断是set,除了特殊情况以外,只要判断l+1到r-1是不是list就行.但注意如果a[l],a[r]不是’{’和’}’,一定不是set.判断是list的复杂些,除了特殊情况(就是atom的情况),还需要判断这一段是不是set(set也是一个list).然后枚举中间的每一位,如果某一位是’,’,那么看它两侧的串是不是两个list,是的话就说明l到r也是list.
实现不难,不过写错了一点,把l+1打成了l+r.winsty说的没错,一定要小心啊…刷1Y率是关键…
{ SPOJ 384; Any fool can do it; FOOL - sqybi’s code - DP}program fool_sqybi; const nn = 200;
var a: string; times, cases, n: longint; dset, dlist: array[1..nn, 1..nn]of longint;
procedure flist(l, r: longint); forward;
procedure fset(l, r: longint); begin if l = r then begin dset[l, r] := […]
Read Full Post |
Make a Comment ( 2 so far )
Posted on 四月 21st, 2008.
题目描述看这段聊天记录:
Killa.sqybi 22:29:21就是说…两排点Killa.sqybi 22:29:38左边那排每个点都有一条边连向右边那排的某个点Killa.sqybi 22:29:45然后每个点有一些权值Killa.sqybi 22:30:05选取一些边Killa.sqybi 22:30:15然后这些边上的点组成一个集合Killa.sqybi 22:30:38要求这个集合的权值之和不能超过PKilla.sqybi 22:30:45问最多选取几个左边的点
看起来很简单的题啊…我刚开始想用网络流,结果问MaShuo,他说是DP…然后我就突然想到怎么做了…
Killa.sqybi 23:39:14首先啊..把所有左边的点按照连到右边点的顺序重新排序Killa.sqybi 23:39:55然后d[i,j]表示排序后左边前i个点选j个的最小花费Killa.sqybi 23:39:57和p比一下..
实现上还有一些小的注意事项,比如有的右边的点和左边的任意一个点没有连边,所以f()里面处理i=j的情况要注意.
WA on 1,8,10,11,11…第六次submit,AC了…
{ SGU 304; Mars Stomatology - sqybi’s code - DP}//for my winstyprogram sgu304_sqybi; const nn = 600; mm = 600;
var n, m, p, i, j, t, ans, ansx, edgeNum, x, y, temp: longint; a, c, r, next, adj, adjr: array[1..nn]of longint; […]
Read Full Post |
Make a Comment ( None so far )
Posted on 四月 21st, 2008.
很赞的状态压缩DP题目…用d[s={1, 0, 1, 0, …}, j, k]表示当前选择情况为s,最后一个选的字符串是j,j放在原先字符串的左边/右边(k=1 or 2)的最小长度.每次取出字符串放到以前放好的字符串前面,比如以前凑好的字符串是abcdcba,现在的字符串是dab,那么就把dab接到原先字符串的左边,就是dabcdcbad.预处理b[i, j, k, p],表示第i个字符串接在左边/右边,第k个字符串接在第i个字符串外面的左边/右边时伸出的最小长度.比如字符串i是abc,k是dab,那么b[i, 1, k, 1]就是1(只有一个d伸出来),而b[i, 1, k, 2]就是3(dab都要伸出来,没有重合部分).
细节方面有很多问题,首先是预处理要删除所有包含关系的字符串只保留最长的,这里如果有两个字符串一样长那么我原来的程序就一个都不会保留.还有预处理时,一个字符串自己生成回文串可能有正反两种情况,我搞错了(就是abc可能生成abcba和cbabc).另外输出结果的时候,print过程对于最中间字符串的处理也有些问题.经过hrm的精心调教和我努力的改程序(虽说代码是越改越恶心=.=),这道WA on test 8许久的题目终于AC了…hrm我爱死你了…
嗯…附代码…建议别看…会恶心死的.
{ SGU 327; Yet Another Palindrome - sqybi’s code - 状态压缩DP}//for my winstyprogram sgu327_sqybi; const nn = 14; mm = 30; unable = nn * mm * 100; type TStr = string[mm];
var n, […]
Read Full Post |
Make a Comment ( None so far )
« Previous Entries