《算法竞赛入门经典训练指南》动态规划习题2

9月 16

动态规划习题(2)

划分成回文串（Partitioning by Palindromes, Uva 11584）

简单动态规划，用dp[i]表示前i部分的划分情况。记录每个点j，以j为中点的回文串长度，然后dp[i]=min(dp[i-s-1]|其中a[i-s~i]为回文串)

Uva 11584 Partitioning by Palindromesview raw

#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

#define zero(a) memset(a,0,sizeof(a))
#define one(a) memset(a,1,sizeof(a))
#define fone(a) memset(a,-1,sizeof(a))
#define setmax(a) memset(a,0x7f,sizeof(a))
#define pow2(a) ((a)*(a))
#define pow3(a) ((pow2(a))*(a))

const int maxn=1005;
char s[maxn];
int dp[maxn];
int hw[maxn];
int hw2[maxn];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%s",s+1);
		int l=strlen(s+1);
		int i,j;
		for(i=1;i<=l;i++)
		{
			hw[i]=hw2[i]=0;
			for(j=0;i+j<=l&&i-j>0;j++)
			{
				if(s[i+j]==s[i-j])
					hw[i]++;
				else
					break;
			}
			for(j=0;i+j+1<=l&&i-j>0;j++)
			{
				if(s[i+j+1]==s[i-j])
					hw2[i]++;
				else
					break;
			}
		}
		zero(dp);
		for(i=1;i<=l;i++)
		{
			dp[i]=dp[i-1]+1;
			for(j=1;j<i;j++)
			{
				if(hw[j]+j-1>=i)
					dp[i]=min(dp[i],dp[2*j-i-1]+1);
				if(hw2[j]+j>=i)
					dp[i]=min(dp[i],dp[2*j-i]+1);
			}
		}
		printf("%d\n",dp[l]);
	}
    return 0;
}

商人（Salesmen, LA 4256）

简单动态规划

LA 4256 Salesmenview raw

#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;

#define zero(a) memset(a,0,sizeof(a))
#define one(a) memset(a,1,sizeof(a))
#define fone(a) memset(a,-1,sizeof(a))
#define setmax(a) memset(a,0x7f,sizeof(a))

vector<int>v[105];
int dp[205][105];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		int i,j;
		for(i=1;i<=n;i++)
			v[i].clear();
		for(i=1;i<=m;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			v[a].push_back(b);
			v[b].push_back(a);
		}
		int p;
		scanf("%d",&p);
		setmax(dp);
		for(i=0;i<=n;i++)
			dp[0][i]=0;
		for(i=1;i<=p;i++)
		{
			int k;
			scanf("%d",&k);
			for(j=1;j<=n;j++)
			{
				int bl=0;
				if(j==k)
					bl=0;
				else
					bl=1;
				dp[i][j]=dp[i-1][j]+bl;
				for(int d=0;d<v[j].size();d++)
				{
					dp[i][j]=min(dp[i][j],dp[i-1][v[j][d]]+bl);
				}
			}
		}
		int ans=1000000000;
		for(i=1;i<=n;i++)
		{
			ans=min(dp[p][i],ans);
		}
		printf("%d\n",ans);
	}
    return 0;
}

波浪子序列（Wavio Sequence, Uva 10534）

做两次最长上升子序列就可以了

Uva 10534 Wavio Sequenceview raw

#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

#define zero(a) memset(a,0,sizeof(a))
#define one(a) memset(a,1,sizeof(a))
#define fone(a) memset(a,-1,sizeof(a))
#define pow2(a) ((a)*(a))
#define pow3(a) ((pow2(a))*(a))

int a[10005];
int t[10005];
int dp[10005];
int dp2[10005];
const int maxn=0x7fffffff;
int erfen(int i,int j,int k)
{
	while(i<j)
	{
		int m=(i+j)/2+1;
		if(t[m]>=k)
			j=m-1;
		else
			i=m;
	}
	return i;
}
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		int i,j;
		for(i=1;i<=n;i++)
			scanf("%d",&a[i]);

		zero(dp);
		zero(dp2);
		zero(t);

		j=0;
		t[0]=-maxn;
		for(i=1;i<=n;i++)
		{
			if(a[i]>t[j])
			{
				j++;
				t[j]=a[i];
				dp[i]=j;
			}
			else
			{
				int k=erfen(0,j,a[i]);
				dp[i]=k+1;
				t[k+1]=a[i];
			}
		}

		zero(t);
		j=0;
		t[j]=-maxn;
		for(i=n;i>0;i--)
		{
			if(a[i]>t[j])
			{
				j++;
				t[j]=a[i];
				dp2[i]=j;
			}
			else
			{
				int k=erfen(0,j,a[i]);
				dp2[i]=k+1;
				t[k+1]=a[i];
			}
		}

		int ans=0;
		for(i=1;i<=n;i++)
			ans=max(ans,2*min(dp[i],dp2[i])-1);
		printf("%d\n",ans);
	}
    return 0;
}