又来发解题报告了
这回是树状DP
/*
* 树状DP
* 首先把数据想象成树状的
* 由于输入数据为树状，不需要构建树
* 可令degree[i]为包括i且以i为根节点的所有子节点数量
* dp[i]为删除i后的最大子节点数量或父亲节点数量 （这里我理解了很久）
*/
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int>chirld[10002];
int dp[10002] = {0}
,degree[10002] = {0}
,isJudged[10002] = {0};
int search(int pos,int &n);
int main()
{
int n,i,a,b;
bool isnone = true;
scanf("%d",&n);…题目链接: http://acm.pku.edu.cn/JudgeOnline/bbs?problem_id=2528
这题又是线段树+离散化
慢慢的对离散化有点感觉了,但是这题我还是错了3次
题目大意是一层一层地叠板子,问最后能看到几块
输入是板子的开始和结束位置
由于输入的是闭区间线段开始我就构造闭区间线段的线段树,但是后来发现很多问题,
题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=3277
线段树+离散化
ACM预选赛过去了,可是我们队什么都没拿到,这给我们的打击是相当大的,这也很大程度上体现了我们的不足
一直没能静下心,来,今天决定不能再这么悲伤下去,我要奋斗,继续学习,就从之前的断点线段树开始
题目链接http://acm.pku.edu.cn/JudgeOnline/problem?id=2549
这道题伤了我很久脑筋
因为是a+b+c=d,数据量是1000,很自然地想到a+b=d-c
这样转化为n^2的算法.
但是我开始枚举d-c的集合二分查找a+b的几何不知道为什么WA掉了
后面就想其他的办法,参考了一下别人的做法,我觉得差不多和我一样,然后重写.我也和他一样无耻的用STL库函数了
POJ打破传统,以前是做一题送一题,现在是做一题送两题,那么我们就不用客气了
言归正传 题号:2606 Rabbit hunt 2780 Linearity 1118 Lining Up
大致题意是输入N个点.计算能穿过最多的点的直线,并输出最大点的个数
最初的想法很简单
枚举没两个点连成的直线,然后枚举每个点,计算通过这条直线的点的个数,但是这个方法的复杂度为O(n^3)
这题是一道DP问题,我的想法如下:
1.可以令 deleteNum[pos]为输入字符串在pos处需要删除的最少字符数量;
2.如果输入字符串长度为len,则初始化deleteNum[len] = 0;(字符串由0开始计数)