首页 > ACM题库 > HDU-杭电 > HDU 1554 Pairs of integers-动态规划-[解题报告] C++
2013
12-12

HDU 1554 Pairs of integers-动态规划-[解题报告] C++

Pairs of integers

问题描述 :

You are to find all pairs of integers such that their sum is equal to the given integer number N and the second number results from the first one by striking out one of its digits. The first integer always has at least two digits and starts with a non-zero digit. The second integer always has one digit less than the first integer and may start with a zero digit.

输入:

The input file consists of several test cases.

Each test case contains single integer N (10 ≤ N ≤ 10^9), as decribed above

输出:

The output consists of several blocks, one for each test case.

On the first line of a block write the total number of different pairs of integers that satisfy the problem statement. On the following lines write all those pairs. Write one pair on a line in ascending order of the first integer in the pair. Each pair must be written in the following format:

X + Y = N

Here X, Y, and N, must be replaced with the corresponding integer numbers. There should be exactly one space on both sides of ‘+’ and ‘=’ characters.

样例输入:

302

样例输出:

5
251 + 51 = 302
275 + 27 = 302
276 + 26 = 302
281 + 21 = 302
301 + 01 = 302

题意:给定若干字符串,输出每个字符串的回文子串个数,这里回文串在原字符串中必须是连续的。

思路:用f(i,j)代表str[i....j]是不是回文串,容易得出递推式f(i,j)=f(i+1,j-1) && str[i]==str[j],然后将所有的f(i,j)加起来就是答案了。(注意f(i,i)=1和i+1>j-1的情况)

但是这个题目开5000*5000的数组会MLE。于是注意到每次f(i,j)只需要用到f(i+1,j-1),即它的前两层的状态,所以只要开一个5000*3的滚动数组就可以了。

当然这题还有更好的方法不过我还没想到~

#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 5005
using namespace std;
int f[MAXN][3],n,ans;
char s[MAXN];
void getf()
{
	n=strlen(s),ans=0;
	for(int k=0;k<n;++k)
		for(int i=0;i+k<n;++i)
		{
		  int j=i+k,now=k%3,pre2=(now-2+3)%3;//pre记录的是f(i,j)的上两层,这里的f[i+1][pre2]指的是f(i+1,j-1)
		  f[i][now]=(k==0 || (k==1 && s[i]==s[j]) || (i+1<=j-1 && s[i]==s[j] && f[i+1][pre2]));
                  //k==0还有k=1都要特殊处理,防止i+1>j-1

                  ans+=f[i][now];
		}
}
int main()
{
	while(~scanf("%s",s))
	{
		getf();
		cout<<ans<<endl;
	}
}


解题报告转自:http://blog.csdn.net/blzorro/article/details/9746935


  1. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。