hdoj3065

注意:多组case。。。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
using namespace std;
#define maxn 700000
typedef struct Trie{
	int count;
	int next[27];
}Trie;
Trie trie[maxn+10];
int fail[maxn+10];
int sz=1;
char s[2000000+10];
int cnt[1000+10];
void init()
{
	int i;
	for(i=1;i<=26;i++)
		trie[0].next[i]=-1;
	memset(fail,0,sizeof(fail));
	trie[0].count=0;
	return;
}
void insert(char s[],int type)
{
	int i;
	int len=strlen(s);
	int p=0;
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-'A'+1;
		if(trie[p].next[x]!=-1)
		{
			p=trie[p].next[x];
		}
		else
		{
			trie[p].next[x]=sz++;
			p=trie[p].next[x];
			for(int j=1;j<=26;j++)
				trie[p].next[j]=-1;
			trie[p].count=0;
		}
	}
	trie[p].count=type;
	return;
}
void build_ac()
{
	queue<int> q;
	fail[0]=0;
	int i;
	for(i=1;i<=26;i++)
		if(trie[0].next[i]!=-1)
		{
			fail[trie[0].next[i]]=0;
			q.push(trie[0].next[i]);
		}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(i=1;i<=26;i++)
		{
			int v=trie[u].next[i];
			if(v!=-1)
			{
				q.push(v);
				int j=fail[u];
				while(j && trie[j].next[i]==-1)
					j=fail[j];
				if(trie[j].next[i]!=-1)
					j=trie[j].next[i];
				fail[v]=j;
			}
		}
	}
	return;
}
void find(char s[])
{
	int i,p,cur=0;
	int len=strlen(s);
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-'A'+1;
		if(s[i]<'A' || s[i]>'Z')//如果主串不是大写字母,必定会不断失配,最终退到根结点,所以直接设置cur=0,continue即可
		{
			cur=0;
			continue;
		}
		while(cur && trie[cur].next[x]==-1)
			cur=fail[cur];
		if(trie[cur].next[x]!=-1)
		{
			cur=trie[cur].next[x];
			p=cur;
			while(p)
			{
				if(trie[p].count!=0)
					cnt[trie[p].count]++;
				p=fail[p];
			}
		}
	}
	return;
}
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		getchar();
		int i;
		init();
		memset(cnt,0,sizeof(cnt));
		char t[1000+10][55];
		for(i=1;i<=n;i++)
		{
			gets(t[i]);
			insert(t[i],i);
		}
		build_ac();
		gets(s);
		find(s);
		for(i=1;i<=n;i++)
			if(cnt[i]!=0)
				printf("%s: %d\n",t[i],cnt[i]);

	}
//system("pause");
return 0;
}

hdoj2896

终于ac了,有在细节上出了纰漏。。累死了,明天记下要点

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<set>
#include<iostream>
using namespace std;
#define maxn 100000
typedef struct Trie{
	int count;
	int next[130+10];
}Trie;
Trie trie[maxn+10];
int fail[maxn+10];
int sz=1;
set<int> ss;
set<int> ::iterator iter;
void init()
{
	int i;
	for(i=1;i<=130;i++)
		trie[0].next[i]=-1;
	memset(fail,0,sizeof(fail));
	trie[0].count=0;
	return;
}
void insert(char s[],int type)
{
	int i;
	int len=strlen(s);
	int p=0;
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-' '+1;
		if(trie[p].next[x]!=-1)
		{
			p=trie[p].next[x];
		}
		else
		{
			trie[p].next[x]=sz++;
			p=trie[p].next[x];
			for(int j=1;j<=130;j++)
				trie[p].next[j]=-1;
			trie[p].count=0;
		}
	}
	trie[p].count=type;
	return;
}
void build_ac()
{
	queue<int> q;
	fail[0]=0;
	int i;
	for(i=1;i<=130;i++)
		if(trie[0].next[i]!=-1)
		{
			fail[trie[0].next[i]]=0;
			q.push(trie[0].next[i]);
		}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(i=1;i<=130;i++)
		{
			int v=trie[u].next[i];
			if(v!=-1)
			{
				q.push(v);
				int j=fail[u];
				while(j && trie[j].next[i]==-1)
					j=fail[j];
				if(trie[j].next[i]!=-1)
					j=trie[j].next[i];
				fail[v]=j;
			}
		}
	}
	return;
}
void find(char s[])
{
	int i,p,cur=0;
	int len=strlen(s);
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-' '+1;
		while(cur && trie[cur].next[x]==-1)
			cur=fail[cur];
		if(trie[cur].next[x]!=-1)
		{
			cur=trie[cur].next[x];
			p=cur;
			while(p)
			{
				if(trie[p].count!=0)
				ss.insert(trie[p].count);
				p=fail[p];
			}
		}
	}
	return;
}
char t[10000+10];
int main()
{

	init();
	int n;
	int i,j;
	char s[210];
	scanf("%d",&n);
	getchar();
	for(i=1;i<=n;i++)
	{
		gets(s);
		insert(s,i);
	}
	build_ac();
	int m,numofweb=0;
	scanf("%d",&m);
	getchar();
	for(i=1;i<=m;i++)
	{
		ss.clear();
		gets(t);
		find(t);
		if(!ss.empty())
		{
			numofweb++;
			cout<<"web "<<i<<":";
			for(iter=ss.begin();iter!=ss.end();iter++)
			{
				cout<<' '<<*iter;
			}
			cout<<endl;
		}
	}
	cout<<"total: "<<numofweb<<endl;

//system("pause");
return 0;
}

hdoj2222

经过一个星期的挣扎,最后决定暂时放弃trie图,而用ac自动机解题,今天开始做题喽~

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
using namespace std;
#define maxn 1000000
typedef struct Trie{
	int count;
	int next[27];
}Trie;
Trie trie[maxn+10];
int fail[maxn+10];
int sz=1;
char s[1000000+10];
void init()
{
	int i;
	for(i=1;i<=26;i++)
		trie[0].next[i]=-1;
	memset(fail,0,sizeof(fail));
	trie[0].count=0;
	return;
}
void insert(char s[])
{
	int i;
	int len=strlen(s);
	int p=0;
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-'a'+1;
		if(trie[p].next[x]!=-1)
		{
			p=trie[p].next[x];
		}
		else
		{
			trie[p].next[x]=sz++;
			p=trie[p].next[x];
			for(int j=1;j<=26;j++)
				trie[p].next[j]=-1;
			trie[p].count=0;
		}
	}
	trie[p].count++;
	return;
}
void build_ac()
{
	queue<int> q;
	fail[0]=0;
	int i;
	for(i=1;i<=26;i++)
		if(trie[0].next[i]!=-1)
		{
			fail[trie[0].next[i]]=0;
			q.push(trie[0].next[i]);
		}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(i=1;i<=26;i++)
		{
			int v=trie[u].next[i];
			if(v!=-1)
			{
				q.push(v);
				int j=fail[u];
				while(j && trie[j].next[i]==-1)
					j=fail[j];
				if(trie[j].next[i]!=-1)
					j=trie[j].next[i];
				fail[v]=j;
			}
		}
	}
	return;
}
int find(char s[])
{
	int cnt=0;
	int i,p,cur=0;
	int len=strlen(s);
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-'a'+1;
		while(cur && trie[cur].next[x]==-1)
			cur=fail[cur];
		if(trie[cur].next[x]!=-1)
		{
			cur=trie[cur].next[x];
			p=cur;
			while(p && trie[p].count!=-1)
			{
				cnt+=trie[p].count;
				trie[p].count=-1;
				p=fail[p];
			}
		}
	}
	return cnt;
}
int main()
{
	int t;
	int i;
	scanf("%d",&t);
	while(t--)
	{
		init();
		int n;
		scanf("%d",&n);
		getchar();
		for(i=1;i<=n;i++)
		{
			char tmp[60];
			gets(tmp);
			insert(tmp);
		}
		build_ac();
		gets(s);
		int ans=find(s);
		printf("%d\n",ans);


	}
//system("pause");
return 0;
}

ac自动机、trie图、扩展kmp的资料

wc的论文http://wenku.baidu.com/view/d2bc836fb84ae45c3b358cae.html
trie图 http://hi.baidu.com/nlunkxgmnjjkoxr/item/80cae19fad3a04da1a49dfbe

http://richardxx.yo2.cn/articles/%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%B3%BB%E5%88%97%E7%AE%97%E6%B3%95%EF%BC%88%E4%B8%80%EF%BC%89.html

不错的ppt http://www.docin.com/p-437918476.html
zhuzeyuan 2004论文 http://wenku.baidu.com/view/12ebad956bec0975f465e2ac.html

ac自动机模板

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
using namespace std;
#define maxn 10000000
typedef struct Trie{
	int count;
	int next[27];
}Trie;
Trie trie[maxn+10];
int fail[maxn+10];
int sz=1;
void init()//每次用trie前,调用一下
{
	int i;
	for(i=1;i<=26;i++)
		trie[0].next[i]=-1;
	memset(fail,0,sizeof(fail));
	trie[0].count=0;
	return;
}
void insert(char s[])
{
	int i;
	int len=strlen(s);
	int p=0;
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-'a'+1;
		if(trie[p].next[x]!=-1)
		{
			p=trie[p].next[x];
		}
		else
		{
			trie[p].next[x]=sz++;
			p=trie[p].next[x];
			for(int j=1;j<=26;j++)
				trie[p].next[j]=-1;
			trie[p].count=0;
		}
	}
	trie[p].count=1;
	return;
}
void build_ac()
{
	queue<int> q;
	fail[0]=0;
	int i;
	for(i=1;i<=26;i++)
		if(trie[0].next[i]!=-1)
		{
			fail[trie[0].next[i]]=0;
			q.push(trie[0].next[i]);
		}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(i=1;i<=26;i++)
		{
			int v=trie[u].next[i];
			if(v!=-1)
			{
				q.push(v);
				int j=fail[u];
				while(j && trie[j].next[i]==-1)
					j=fail[j];
				if(trie[j].next[i]!=-1)
					j=trie[j].next[i];
				fail[v]=j;
			}
		}
	}
	return;
}
int find(char s[])
{
	int cnt=0;
	int i,p,cur=0;
	int len=strlen(s);
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-'a'+1;
		while(cur && trie[cur].next[x]==-1)
			cur=fail[cur];
		if(trie[cur].next[x]!=-1)
		{
			cur=trie[cur].next[x];
			p=cur;
			while(p && trie[p].count!=-1)//不管当前节点是否是单词的结尾,将它以及fail链上的结点统统标记为已访问(-1)
			{
				cnt+=trie[p].count;//点cur(当前点虽然可能不是单词结点,但是它回溯后的点可能是单词结点(即字符串S[root……cur]的后缀可能是单词结点),所以到达cur点时,可能找到的单词点不止一个,要把他们都计数,并设为-1,防止下次重复计数这些单词点)
				trie[p].count=-1;
				p=fail[p];
			}
		}
	}
	return cnt;
}
int main()
{

	init();
system("pause");
return 0;
}

Trie——第二种静态建树方法

本质和前一种静态数组实现一样,只不过把两个数组ch[][]、v[]合在一个结构体里面了

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxn 10000000
typedef struct Trie{
	int v;
	int next[27];
}Trie;
Trie trie[maxn+10];
int sz=1;
void init()
{
	int i;
	for(i=1;i<=26;i++)
		trie[0].next[i]=-1;
	trie[0].v=0;
	return;
}
void insert(char s[])
{
	int i;
	int len=strlen(s);
	int p=0;
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-'a'+1;
		if(trie[p].next[x]!=-1)
		{
			p=trie[p].next[x];
		}
		else
		{
			trie[p].next[x]=sz++;
			p=trie[p].next[x];
			for(int j=1;j<=26;j++)
				trie[p].next[j]=-1;
			trie[p].v=0;
		}
	}
	trie[p].v=1;
	return;
}
int find(char s[])
{
	int i;
	int p=0;
	int len=strlen(s);
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-'a'+1;
		if(trie[p].next[x])
			p=trie[p].next[x];
		else
			return trie[p].v;
	}
		return trie[p].v;

}
int main()
{

	init();//每次使用trie前先init()
	/*
	char word[20];
	gets(word);
	while(word[0]!='\0' && word[0]!=' ')
	{
		insert(word);
		gets(word);
	}
	while(gets(query))
	{
		int ans=find(query);
		printf("%d\n",ans);
		

	}
	*/
system("pause");
return 0;
}

hdoj1251——用第二种静态trie写法解决

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Trie{
	int v;
	int next[27];
}Trie;
Trie trie[10000000];
int sz=1;
void init()
{
	int i;
	for(i=1;i<=26;i++)
		trie[0].next[i]=-1;
	trie[0].v=0;
	return;
}
void insert(char s[])
{
	int i;
	int len=strlen(s);
	int p=0;
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-'a'+1;
		if(trie[p].next[x]!=-1)
		{
			p=trie[p].next[x];
			trie[p].v++;
		}
		else
		{
			trie[p].next[x]=sz++;
			p=trie[p].next[x];
			for(int j=1;j<=26;j++)
				trie[p].next[j]=-1;
			trie[p].v=1;
		}
	}
	return;
}
int find(char s[])
{
	int i;
	int p=0;
	int len=strlen(s);
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-'a'+1;
		if(trie[p].next[x])
			p=trie[p].next[x];
		else
			return 0;
	}
		return trie[p].v;

}
char query[1000010];
int main()
{
	char word[20];
	init();
	gets(word);
	while(word[0]!='\0' && word[0]!=' ')
	{
		insert(word);
		gets(word);
	}
	while(gets(query))
	{
		int ans=find(query);
		printf("%d\n",ans);
		

	}
system("pause");
return 0;
}

hdoj1298

这题写的真可谓心力憔悴,写了好长时间。。trie+dfs
最后还是TLE,不管了,先放上TLE代码。。以后再说

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxn 100000
typedef struct Trie{
	int ch[maxn][27];
	int v[maxn];
	int sz;
	Trie()
	{
		memset(ch[1],0,sizeof(ch[1]));
		memset(v,0,sizeof(v));
		sz=1;
	}
	void init()
	{
		memset(ch,0,sizeof(ch));
		memset(v,0,sizeof(v));
		sz=1;
	}
	void insert(char s[],int value)
	{
		int i;
		int u=1;
		int len=strlen(s);
		for(i=0;i<=len-1;i++)
		{
			int x=s[i]-'a'+1;
			if(ch[u][x]==0)
			{
				sz++;
				memset(ch[sz],0,sizeof(ch[sz]));
				ch[u][x]=sz;
				v[sz]+=value;
			}
			else
			{
				v[ch[u][x]]+=value;
			}
			u=ch[u][x];
		}
		return;
	}
	int find(char s[])
	{
		int i;
		int u=1;
		int len=strlen(s);
		for(i=0;i<=len-1;i++)
		{
			int x=s[i]-'a'+1;
			if(ch[u][x]==0)
				return -1;
			else
				u=ch[u][x];
		}
		return v[u];
	}
}Trie;
Trie trie;
char num[12][10];
char anstmp[110];
int max=-1;
void dfs(int cur,char ss[],int len,char* ans)
{
	int i;
	if(cur==len+1)
	{
		anstmp[cur]='\0';
		int tmp=trie.find(anstmp);
		if(tmp>max)
		{
			max=tmp;
			strcpy(ans,anstmp);
		}
		return;
	}
	int number=ss[cur]-'1'+1;
	for(i=1;i<=4;i++)
	{
		if(i!=4)
		{
			anstmp[cur]=num[number][i];
			dfs(cur+1,ss,len,ans);
		}
		else
		{
			if(number==7 || number==9)
			{
				anstmp[cur]=num[number][i];
				dfs(cur+1,ss,len,ans);
			}
		}
	}
	return;

}

int main()
{
	int t,cases=0;
	int i,j;
	char zimu[30];
	for(i=1;i<=26;i++)
		zimu[i]='a'+i-1;
	int cnt=0;
	for(i=2;i<=9;i++)
		for(j=1;j<=4;j++)
		{
			if(j!=4)
				num[i][j]=zimu[++cnt];	
			else
			{
				if(i==7 || i==9)
					num[i][j]=zimu[++cnt];
			}
		}
	scanf("%d",&t);
	
	while(t--)
	{
		trie.init();
		int n;
		int v;
		char s[110];
		scanf("%d",&n);
		getchar();
		for(i=1;i<=n;i++)
		{
			scanf("%s %d",s,&v);
			getchar();
			trie.insert(s,v);
		}
		int m;
		char ss[110];
		scanf("%d",&m);
		getchar();
		printf("Scenario #%d:\n",++cases);
		for(i=1;i<=m;i++)
		{
			gets(ss);
			int len=strlen(ss);
			ss[len-1]='\0';
			for(j=0;j<=len-2;j++)
			{
				char ans[110];
				max=-1;
				dfs(0,ss,j,ans);
				if(max!=-1)
					printf("%s\n",ans);
				else
					printf("MANUALLY\n");
			}
			printf("\n");
		}
		printf("\n");
	}
	//system("pause");
	return 0;
}

hdoj2059——龟兔赛跑

再一次给dp跪了,想的太复杂,思维乱作一团。上网看了解题报告,这才恍然大悟
思路:dp[i]表示到达第i个加油站时最少使用时间(附设dp[0]表示起点,dp[n+1]表示终点),对于dp[i],它一定是由某个(第j个)加油站(j<=i-1,j可能为0,也就是可能为起点)加油后一路驶来的,开始我对这里有个疑惑,为什么不是由第j个加油站不加油驶来的呢?呵呵~,其实如果是从第j个加油站不加油驶来也就意味着它肯定是由j之前的某个加油站加油驶来(就算没有在任何一个加油站加油,那么把起点看成第0个加油站,它起码是从第0个加油站加油驶来(注意此种情况下不需要加上时间t,因为起点的油本来就是满的))。初始化的时候dp[]设置为从第0个加油站(起点)加油后驶来的时间。

#include<stdio.h>
#include<stdlib.h>
int main()
{
	int L;
	int i,j;
	while(scanf("%d",&L)!=EOF)
	{
		int n,c,t;
		scanf("%d %d %d",&n,&c,&t);
		int vr,vh,vl;
		scanf("%d %d %d",&vr,&vh,&vl);
		int p[110];
		for(i=1;i<=n;i++)
		{
			scanf("%d",&p[i]);
		}
		p[0]=0;
		p[n+1]=L;
		double dp[110];
		dp[0]=0;
		for(i=1;i<=n+1;i++)
		{
			if(p[i]<=c)
			{
				dp[i]=(p[i]*1.0)/vh;	
			}
			else
			{
				dp[i]=(c*1.0)/vh+(1.0*(p[i]-c))/vl;
			}
		
		}
		for(i=1;i<=n+1;i++)
		{
			for(j=1;j<=i-1;j++)
			{
				double tmp;
				if(p[i]-p[j]<=c)
				{
					tmp=dp[j]+((p[i]-p[j])*1.0)/vh+(double)t;
				}
				else
					tmp=dp[j]+(c*1.0)/vh+((p[i]-p[j]-c)*1.0)/vl+(double)t;
				if(tmp<dp[i])
					dp[i]=tmp;
			}
		}
		double ans=(L*1.0)/vr;
		if(dp[n+1]<ans)
			printf("What a pity rabbit!\n");
		else
			printf("Good job,rabbit!\n");
	}

//system("pause");
return 0;
}

hdoj1789

思路:先按分值从大到小排序,然后从前往后一一考虑每个任务能否完成,若可以完成,则完成那天越靠后越好,这样可以为其它任务留下最大的余地。
标注:这题还有一些不明白的地方,回头须细细复习琢磨。。

#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
using namespace std;
typedef struct work{
	int time;
	int score;
}work;
bool cmp(work a,work b)
{
	if(a.score!=b.score)
		return a.score>b.score;
	return a.time<b.time;
}
bool day[10000000];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		int i,j;
		work w[1010];
		for(i=1;i<=n;i++)
			scanf("%d",&w[i].time);
		for(i=1;i<=n;i++)
			scanf("%d",&w[i].score);
		sort(w+1,w+1+n,cmp);
		int ans=0;
		memset(day,0,sizeof(day));
		for(i=1;i<=n;i++)
		{
			for(j=w[i].time;j>=1;j--)
				if(day[j]==0)
				{
					day[j]=1;
					break;
				}
			if(j==0)
				ans+=w[i].score;
		}
		printf("%d\n",ans);

	
	
	
	}

//system("pause");
return 0;
}

hdoj1830

    可以说这题依然是前面最大子矩阵的加强版,这一次列之间可以无限交换。

    思路:枚举以每一行为底,这样可以求出h[]数组。因为列可以交换所以将h[]数组降序排列,显然以h[1]为高的矩形面积是h[1]*1,以h[2]为高的矩形面积是h[2]*2……。找出这些矩形中最大的即为以i行为底的h[]数组所能形成的最大子矩阵,剩下的就是枚举行

 

 

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char map[1010][1010];
int h[1010];
bool cmp(int a,int b)
{
	return a>b;
}
int cal(int h[],int m)
{
	int i;
	int ans=-1;
	for(i=1;i<=m;i++)
	{
		int tmp=h[i]*i;
		if(tmp>ans)
			ans=tmp;
	}
	return ans;
}
int main()
{
	int n,m;
	int i,j,k;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		getchar();
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				scanf("%c",&map[i][j]);
			}
			getchar();
		}
		int ans=-1;
		for(i=1;i<=n;i++)
		{
			memset(h,0,sizeof(h));
			for(j=1;j<=m;j++)
			{
				for(k=i;k>=1;k--)
				{
					if(map[k][j]=='1')
						h[j]++;
					else
						break;
				
				}
			}
			sort(h+1,h+1+m,cmp);
			int tmp=cal(h,m);
			if(tmp>ans)
				ans=tmp;
		}
		printf("%d\n",ans);
	
	}

//system("pause");
return 0;
}

HDU 动态规划(46道题目)倾情奉献~ 【只提供思路与状态转移方程】(转载)

转自:http://www.cppblog.com/doer-xee/archive/2009/12/05/102629.html
Robberies http://acm.hdu.edu.cn/showproblem.php?pid=2955
    背包;第一次做的时候把概率当做背包(放大100000倍化为整数):在此范围内最多能抢多少钱  最脑残的是把总的概率以为是抢N家银行的概率之和… 把状态转移方程写成了f[j]=max{f[j],f[j-q[i].v]+q[i].money}(f[j]表示在概率j之下能抢的大洋);
    
    正确的方程是:f[j]=max(f[j],f[j-q[i].money]*q[i].v)  其中,f[j]表示抢j块大洋的最大的逃脱概率,条件是f[j-q[i].money]可达,也就是之前抢劫过;
    始化为:f[0]=1,其余初始化为-1  (抢0块大洋肯定不被抓嘛)
    
最大报销额 http://acm.hdu.edu.cn/showproblem.php?pid=1864
    又一个背包问题,对于每张发票,要么报销,要么不报销,0-1背包,张数即为背包;
    转移方程:f[j]=max(f[j],f[j-1]+v[i]);
    恶心地方:有这样的输入数据 3 A:100 A:200 A:300
    
最大连续子序列 http://acm.hdu.edu.cn/showproblem.php?pid=1231
    状态方程:sum[i]=max(sum[i-1]+a[i],a[i]);最后从头到尾扫一边
    也可以写成:
                Max=a[0];
                Current=0;
                for(i=0;i<n;i++)
                {
                    if(Current<0)
                        Current=a[i];
                    else
                        Current+=a[i];
                    if(Current>Max)
                        Max=Current;
                }
    
max sum http://acm.hdu.edu.cn/showproblem.php?pid=1003
    同上,最大连续子序列    
    
Largest Rectangle http://acm.hdu.edu.cn/showproblem.php?pid=1506
    对于每一块木板,Area=height[i]*(j-k+1)  其中,j<=x<=k,height[x]>=height[i];找j,k成为关键,一般方法肯定超时,利用动态规划,如果它左边高度大于等于它本身,那么它左边的左边界一定满足这个性质,再从这个边界的左边迭代下去
    for(i=1;i<=n;i++)
        {            
            while(a[l[i]-1]>=a[i])
                l[i]=l[l[i]-1];
                
        }
    
    for(i=n;i>=1;i–)
        {
            while(a[r[i]+1]>=a[i])
                r[i]=r[r[i]+1];
        }
    
City Game http://acm.hdu.edu.cn/showproblem.php?pid=1505
    1506的加强版,把2维转换化成以每一行底,组成的最大面积;(注意处理连续与间断的情况);
    
Bone Collector http://acm.hdu.edu.cn/showproblem.php?pid=2602
    简单0-1背包,状态方程:f[j]=max(f[j],f[j-v[i]]+w[i])
    
Super Jumping  http://acm.hdu.edu.cn/showproblem.php?pid=1087
    最大递增子段和,状态方程:sum[j]=max{sum[i]}+a[j]; 其中,0<=i<=j,a[i]     
命运http://acm.hdu.edu.cn/showproblem.php?pid=2571
    状态方程:sum[i][j]=max{sum[i-1][j],sum[i][k]}+v[i][j];其中1<=k<=j-1,且k是j的因子    
    
Monkey And Banana     http://acm.hdu.edu.cn/showproblem.php?pid=1069
    状态方程:f[j]=max{f[i]}+v[j];其中,0<=i<=j,w[i]     
Big Event in HDU http://acm.hdu.edu.cn/showproblem.php?pid=1171
    一维背包,逐个考虑每个物品带来的影响,对于第i个物品:if(f[j-v[i]]==0) f[j]=0;
    其中,j为逆序循环,且j>=v[i]    
    
数塔http://acm.hdu.edu.cn/showproblem.php?pid=2084
    自底向上:dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+v[i][j];    
    
免费馅饼http://acm.hdu.edu.cn/showproblem.php?pid=1176
    简单数塔
    自底向上计算:dp[i][j]=max(dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1])+v[i][j];处理边界
    
I Need A Offer http://acm.hdu.edu.cn/showproblem.php?pid=1203
    简单0-1背包,题目要求的是至少收到一份Offer的最大概率,我们得到得不到的最小概率即可,状态转移方程:f[j]=min(f[j],f[j-v[i]]*w[i]);其中,w[i]表示得不到的概率,(1-f[j])为花费j元得到Offer的最大概率    
    
FATE http://acm.hdu.edu.cn/showproblem.php?pid=2159
    二维完全背包,第二层跟第三层的要顺序循环;(0-1背包逆序循环);状态可理解为,在背包属性为 {m(忍耐度), s(杀怪个数)} 里最多能得到的经验值,之前的背包牺牲体积,这个背包牺牲忍耐度跟个数
    注意: 最后扫的时候 外层循环为忍耐度,内层循环为杀怪个数,因为题目要求出剩余忍耐度最大,没有约束杀怪个数,一旦找到经验加满的即为最优解;
    状态转移方程为: f[j][k]=max(f[j][k],f[j-v[i]][k-1]+w[i]); w[i]表示杀死第i个怪所得的经验值,v[i]表示消耗的忍耐度
    
How To Type http://acm.hdu.edu.cn/showproblem.php?pid=2577     
    用两个a,b数组分别记录Caps Lock开与关时打印第i个字母的最少操作步骤;
    而对于第i个字母的大小写还要分开讨论:
    Ch[i]为小写: a[i]=min(a[i-1]+1,b[i-1]+2);不开灯直接字母,开灯则先关灯再按字母,最后保持不开灯;    b[i]=min(a[i-1]+2,b[i-1]+2);不开灯则先按字母再开灯,开灯则Shift+字母(比关灯,按字母再开灯节省步数),最后保持开灯;
    Ch[i]为大写: a[i]=min(a[i-1]+2,b[i-1]+2); b[i]=min(a[i-1]+2,b[i-1]+1)
    
    最后,b[len-1]++,关灯嘛O(∩_∩)O~     
    
Coins http://acm.hdu.edu.cn/showproblem.php?pid=2844
    类似于HDU1171 Big Event In HDU,一维DP,可达可不达    
    
Beans http://acm.hdu.edu.cn/showproblem.php?pid=2845
    横竖分别求一下不连续的最大子段和;
    状态方程: Sum[i]=max(sum[j])+a[i];其中,0<=j<i-1;    
    
Largest Submatrix http://acm.hdu.edu.cn/showproblem.php?pid=2870
    枚举a,b,c 最大完全子矩阵,类似于HDU1505 1506    
    
Matrix Swapping II http://acm.hdu.edu.cn/showproblem.php?pid=2830
最大完全子矩阵,以第i行为底,可以构成的最大矩阵,因为该题可以任意移动列,所以只要大于等于height[i]的都可以移动到一起,求出height>=height[i]的个数即可,这里用hash+滚动,先求出height[i]出现的次数,然后逆序扫一遍hash[i]+=hash[i+1];    
    
最少拦截系统http://acm.hdu.edu.cn/showproblem.php?pid=1257
    两种做法,一是贪心,从后往前贪;二是DP;
    if(v[i]>max{dp[j]})  (0<=j<len)
    dp[len++]=v[i];    
    
Common Subsequence http://acm.hdu.edu.cn/showproblem.php?pid=1159
    经典DP,最长公共子序列
    Len[i][j]={len[i-1][j-1]+1,(a[i]==b[j]); max(len[i-1][j],len[i][j-1])}
    初始化的优化:
    for(i=0;i<a;i++)
            for(j=0;j<b;j++)
                len[i][j]=0;
        for(i=1;i<=a;i++)
            for(j=1;j<=b;j++)
                if(ch1[i-1]==ch2[j-1])
                    len[i][j]=len[i-1][j-1]+1;
                else
                    len[i][j]=max(len[i-1][j],len[i][j-1]);    
    
★ 搬寝室http://acm.hdu.edu.cn/showproblem.php?pid=1421
    状态Dp[i][j]为前i件物品选j对的最优解
    当i=j*2时,只有一种选择即 Dp[i-2][j-1]+(w[i]-w[i-1])^2
    当i>j*2时,Dp[i][j] = min(Dp[i-1][j],Dp[i-2][j-1]+(w[j]-w[j-1])^2)    
    
★ Humble Numbers http://acm.hdu.edu.cn/showproblem.php?pid=1058
    如果一个数是Humble Number,那么它的2倍,3倍,5倍,7倍仍然是Humble Number
    定义F[i]为第i个Humble Number
    F[n]=min(2*f[i],3*f[j],5*f[k],7*f[L]), i,j,k,L在被选择后相互移动
    (通过此题理解到数组有序特性)    
    
★ Doing Homework Again http://acm.hdu.edu.cn/showproblem.php?pid=1789
有待思考
    这题为贪心,经典题;
    切题角度,对于每个任务要么在截至日期前完成要么被扣分;所以考虑每个人物的完成情况即可;由于每天只能完成一个任务,所以优先考虑分值较大的任务,看看该任务能不能完成,只要能完成,即使提前完成,占了其他任务的完成日期也没关系,因为当前任务的分值最大嘛,而对于能完成的任务能拖多久就拖多久,以便腾出更多时间完成其他任务;    
    
How Many Ways http://acm.hdu.edu.cn/showproblem.php?pid=1978
    两种D法,一是对于当前的点,那些点可达;二是当前点可达那些点;
    明显第二种方法高,因为第一种方法有一些没必要的尝试;
    Dp[i][j]+=Dp[ii][jj]; (map[ii][jj]>=两点的曼哈顿距离)
    值得优化的地方,每两点的曼哈顿距离可能不止求一次,所以预处理一下直接读取    
    
珍惜现在 感恩生活http://acm.hdu.edu.cn/showproblem.php?pid=2191
    每个物品最多可取n件,多重背包;
    利用二进制思想,把每种物品转化为几件物品,然后就成为了0-1背包    
    
Piggy-Bank http://acm.hdu.edu.cn/showproblem.php?pid=1114
    完全背包;常规背包是求最大值,这题求最小值;
    只需要修改一下初始化,f[0]=0,其他赋值为+∞即可;
    状态转移方程:f[i][V]=max{f[i-1][V],f[i-1][V-k*v[i]]+k*w[i]},其中0<=k*v[i]<=V
    
★ Max Sum Plus Plus http://acm.hdu.edu.cn/showproblem.php?pid=1024

    1. 对于前n个数, 以v[n]为底取m段:
    当n==m时,Sum[m][n]=Sum[m-1][n-1]+v[n],第n个数独立成段;
当n>m时, Sum[m][n]=max{Sum[m-1][k],Sum[m][n-1]}+v[n]; 其中,m-1<=k 2. 空间的优化:
        通过状态方程可以看出,取m段时,只与取m-1段有关,所以用滚动数组来节省空间
    
FatMouse’s Speed http://acm.hdu.edu.cn/showproblem.php?pid=1160
    要求:体重严格递增,速度严格递减,原始顺序不定
    按体重或者速度排序,即顺数固定后转化为最长上升子序列问题
    Dp[i]表示为以第i项为底构成的最长子序列,Dp[i]=max(dp[j])+1,其中0<=jw[j]&&s[i]     
Cstructing Roads http://acm.hdu.edu.cn/showproblem.php?pid=1025
    以p或者r按升序排列以后,问题转化为最长上升子序列
    题目数据量比较大,只能采取二分查找,n*log(n)的算法
用一个数组记录dp[]记录最长的子序列,len表示长度,如果a[i]>dp[len], 则接在后面,len++; 否则在dp[]中找到最大的j,满足dp[j]     
FatMouse Chees http://acm.hdu.edu.cn/showproblem.php?pid=1078
    Dp思想,用记忆化搜索;简单题,处理好边界;    
    
To the Max http://acm.hdu.edu.cn/showproblem.php?pid=1081
    最大子矩阵
    把多维转化为一维的最大连续子序列;(HDU1003)    
    
龟兔赛跑http://acm.hdu.edu.cn/showproblem.php?pid=2059
未总结    
    
★ Employment Planning http://acm.hdu.edu.cn/showproblem.php?pid=1158
    状态表示:    Dp[i][j]为前i个月的留j个人的最优解;Num[i]<=j<=Max{Num[i]};
                j>Max{Num[i]}之后无意义,无谓的浪费 记Max_n=Max{Num[i]};
    Dp[i-1]中的每一项都可能影响到Dp[i],即使Num[i-1]<     所以利用Dp[i-1]中的所有项去求Dp[i];
    对于Num[i]<=k<=Max_n,    当k<j时, 招聘;
                            当k>j时, 解雇  然后求出最小值
    Dp[i][j]=min{Dp[i-1][k…Max_n]+(招聘,解雇,工资);    
    
Dividing http://acm.hdu.edu.cn/showproblem.php?pid=1059
    一维Dp  Sum为偶数的时候判断Dp[sum/2]可不可达    
    
Human Gene Factions http://acm.hdu.edu.cn/showproblem.php?pid=1080
状态转移方程:
f[i][j]=Max(f[i-1][j-1]+r[a[i]][b[j]], f[i][j-1]+r[‘-‘][b[j]],f[i-1][j]+r[a[i]][‘-‘]);

★ Doing Homework http://acm.hdu.edu.cn/showproblem.php?pid=1074
    这题用到位压缩;
    那么任务所有的状态有2^n-1种
    状态方程为:Dp[next]=min{Dp[k]+i的罚时} 其中,next=k+(1<<i),k要取完满足条件的值 k>>i的奇偶性决定状态k
具体实现为: 对每种状态遍历n项任务,如果第i项没有完成,则计算出Dp[next]的最优解    
    
Free DIY Tour http://acm.hdu.edu.cn/showproblem.php?pid=1224
    简单的数塔Dp,考察的是细节的处理;
    Dp[i]=Max{Dp[j]}+v[i]  其中j->i为通路;
    v[n+1]有没有初始化,Dp数组有没有初始化
    这题不能用想当然的”最长路”来解决,这好像是个NP问题 解决不了的
    
    
重温世界杯http://acm.hdu.edu.cn/showproblem.php?pid=1422
这题的状态不难理解,状态表示为,如果上一个城市剩下的钱不为负,也就是没有被赶回杭电,则再考虑它对下一个城市的影响;如果上一个城市剩下的前加上当前城市的前大于当前城市的生活费,那么Dp[i]=Dp[i-1]+1;
值得注意的而是这题的数据为100000;不可能以每个城市为起点来一次Dp,时间复杂度为n^2;足已超时;
我是这样处理的,在保存的数据后面再接上1…n的数据,这样扫描一遍的复杂度为n;再加一个优化,当Dp[i]==n时,也就是能全部游完所有城市的时候,直接break;

Pearls http://acm.hdu.edu.cn/showproblem.php?pid=1300
    Dp[i]=min{Dp[j]+V},  0<=j<i, V为第j+1类珠宝到第i类全部以i类买入的价值;    
    
Zipper http://acm.hdu.edu.cn/showproblem.php?pid=1501
    Dp[i][j]=     
    
★Fast Food http://acm.hdu.edu.cn/showproblem.php?pid=1227(running
    这里需要一个常识:在i到j取一点使它到区间每一点的距离之和最小,这一点为(i+j)/2用图形即可证明;
    Dp[i][j]=max{Dp[i-1][k]+cost[k+1][j]  其中,(i-1)<=k<j状态为前j个position建i个depots    
    
Warcraft http://acm.hdu.edu.cn/showproblem.php?pid=3008
    比赛的时候这道DP卡到我网络中心停电!!! 卧槽~
    因为你没有回血效应,所以你挂掉的时间是一定的;
    用Dp[i][j]表示第i秒剩余j个单位的MP时怪物所剩的血量; 注意必须是剩余,也就是说,初始化的时候,DP[0][100]=100;  其他Dp[0]状态都不合法,因为没有开战的时候你的MP是满的
    状态转移方程为:
    Dp[i+1][j-sk[k].mp+x]=min(Dp[i+1][j-sk[k].mp+x],Dp[i][j]+sk[k].at; 释放第K种技能,物理攻击可以看成是at=1,mp=0 的魔法;
    
Regular Words http://acm.hdu.edu.cn/showproblem.php?pid=1502
    F[a][b]=F[a-1][b]+F[a][b-1]+F[a][b];
    a>=b>=c;    
    
Advanced Fruits http://acm.hdu.edu.cn/showproblem.php?pid=1503
    最长公共子序列的加强版  

hdoj1978

记忆化搜索,注意要正确的初始化。dp[n][m]=1;

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int n,m;
int map[110][110];
int dp[110][110];
int DP(int x,int y)
{
	if(dp[x][y]!=-1)
		return dp[x][y]%10000;
	dp[x][y]=0;
	int i=x,j=y;
	if(y<=m-1)
	{
		for(j=y+1;j<=y+map[x][y];j++)
		{
			if(j<=m)
				dp[x][y]=(dp[x][y]+DP(i,j))%10000;
		}
	}
	if(x<=n-1)
	{
		for(i=x+1;i<=x+map[x][y];i++)
		{
			if(i<=n)
			{
				for(j=y;j<=y+map[x][y]-(i-(x+1))-1;j++)
				{
					if(j<=m)
						dp[x][y]=(dp[x][y]+DP(i,j))%10000;
				}
			}
		}
	}
	return dp[x][y];
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{

		int i,j;

		memset(dp,-1,sizeof(dp));
		scanf("%d %d",&n,&m);
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
			{
				scanf("%d",&map[i][j]);
			}
		dp[n][m]=1;
		printf("%d\n",DP(1,1));


	}
//system("pause");
return 0;
}