RQNOJ | Comzyh的博客

p44 拼图回溯题解

Posted on 2010年08月2日2010年09月14日 by comzyh

本来是个水题，我一交，WA：90，第一点错误，答案1位选手输出20位。
得，骗数据，共1个物体，4*4大小，推断可能是：
1 4 4 1000 0000 0000 0000
这叫什么数据。。
一定要注意可能n*m的方块没有占用n*m的情况，于是乎，我放上来了
MYCODE:
Continue reading “p44 拼图回溯题解”

P49 加分二叉树题解

Posted on 2010年07月12日2011年05月7日 by comzyh

题目中说二叉树的中序遍历是顺序的，这说明：对于区间[i,j]其根root满足i<=root<=j

也就是说，对于区间[i,j]其最大加分为选取其中一个作为根R，其左边[i,R-1]的最大加分乘以[R+1,j]区间最大加分+Value[R]，对于所有可能的R取表达式最大值.状态转移方程：

\(f[i][j] = Max\left\{ {f[i,k – 1] \times f[k + 1][j] + v[k] ~|~ k = i~to~j} \right\}\)注意：题目要求若一棵树没有左或者右子树，则其加分为存在的那棵子树

初始值for i=1 to n f[i][i]=v[i];

输出便利的方法是：每次记录取到最大值时的根节点编号，设Node[i][j]=x表示在[i][j]区间取到最大加分的数的根节点为x
Continue reading “P49 加分二叉树题解”

P156 吞噬比赛 NlogN最长不下降子序列

Posted on 2010年06月29日2010年10月1日 by comzyh

MY CODE:

#include<stdio.h>
//nlogn算法
/*把10000搞成1000了，错了一下午*/ 
int n,max;
int b[10001],a[10001],len[10001];
 int bins(int key) {
    static int l,r,y;
    l=0;r=n;
    while (l<=r){
          y=(l+r)>>1;
          if (b[y]>key) r=y-1;else
          if (b[y]<key) {if (b[y+1]>key) return y;else l=y+1;}//这里大括号为了阅读方便
          else return y;
          }
    }
int main(){
    int i,j;
    scanf("%d\n",&n);
    for (i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=20000;}
    b[0]=0;//这个初始化要比所有元素小
    for (i=1;i<=n;i++){
         len[i]=bins(a[i]-1)+1;
         if (len[i]>max) max=len[i];
         if (b[len[i]]>a[i]) b[len[i]]=a[i];
         }
        printf("%d",max);
        return 0;       
    }

#include<stdio.h>

//nlogn算法

/*把10000搞成1000了，错了一下午*/

int n,max;

int b[10001],a[10001],len[10001];

int bins(int key) {

static int l,r,y;

l=0;r=n;

while (l<=r){

y=(l+r)>>1;

if (b[y]>key) r=y-1;else

if (b[y]<key) {if (b[y+1]>key) return y;else l=y+1;}//这里大括号为了阅读方便

else return y;

}

int main(){

int i,j;

scanf("%d\n",&n);

for (i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=20000;}

b[0]=0;//这个初始化要比所有元素小

for (i=1;i<=n;i++){

len[i]=bins(a[i]-1)+1;

if (len[i]>max) max=len[i];

if (b[len[i]]>a[i]) b[len[i]]=a[i];

}

printf("%d",max);

return 0;

}

Continue reading “P156 吞噬比赛 NlogN最长不下降子序列”