Breaking Strings
Time Limit: 2 Seconds Memory Limit: 65536 KB
A certain string-processing language allows the programmer to break a string into two pieces. Since this involves copying the old string, it costs n units of time to break a string of n characters into two pieces. Suppose a programmer wants to break a string into many pieces. The order in which the breaks are made can affect the total amount of time used. For example, suppose we wish to break a 20 character string after characters 3, 8, and 10 (numbering the characters in ascending order from the left-hand end, starting from 1). If the breaks are made in left-to-right order, then the first break cost 20 units of time, the second break costs 17 units of time, and the third breaks costs 12 units of time, a total of 49 units of time (see the sample below). If the breaks are made in right-to-left order, then the first break costs 20 units of time, the second break costs 10 units of time, and the third break costs 8 units of time, a total of 38 units of time.
The cost of making the breaks in left-to-right order:
thisisastringofchars (original)
thi sisastringofchars (cost:20 units)
thi sisas tringofchars (cost:17 units)
thi sisas tr ingofchars (cost:12 units)
Total: 49 units.
The cost of making the breaks in right-to-left order:
thisisastringofchars (original)
thisisastr ingofchars (cost:20 units)
thisisas tr ingofchars (cost:10 units)
thi sisas tr ingofchars (cost: 8 units)
Total: 38 units.
Input:
There are several test cases! In each test case, the first line contains 2 integers N (2<=N<=10000000) and M (1<=M<=1000, M<N). N is the original length of the string, and M is the number of the breaks. The following lines contain M integers Mi (1<=Mi<N) in ascending order that represent the breaking positions from the string's left-hand end.
Output:
For each test case, output in one line the least cost to make all the breakings.
Sample Input:
20 3
3 8 10
Sample Output:
37
Author: Wei, Qizheng
Source: ZOJ Monthly, June 200
和那个石子合并成集合竟然是一模一样，字符串就是把整个分成一个个，也可以看成一个个小石子合成一个大的集合！这其实是一样的！所以，要做的就是把整个分成一个个小的块，再合并起来就得到了答案，核心是一样的！
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define MAXN 1050
#define inf 1000000000
int prime[MAXN];
int dp[MAXN][MAXN],kk[MAXN][MAXN],sum[MAXN],p[MAXN];
int main()
{
int n,i,k,j,len,m;
while(scanf("%d%d",&m,&n)!=EOF)
{
p[0]=0;
for(i=1;i<=n;i++)
{
scanf("%d",&p[i]);
prime[i]=p[i]-p[i-1];
sum[i]=sum[i-1]+prime[i];
}
sum[0]=0;
n++;
prime[n]=m-p[n-1];
sum[n]=sum[n-1]+prime[n];
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
{
dp[i][j]=inf;
}
for(i=1;i<=n;i++)
{
dp[i][i]=0;
kk[i][i]=i;
}
for(len=2;len<=n;len++)
{ for(i=1;i<=n-len+1;i++)
{
j=i+len-1; for(k=kk[i][j-1];k<=kk[i+1][j];k++)//此时的k取法不同
{
int temp=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
if(temp<dp[i][j])
{
dp[i][j]=temp;
kk[i][j]=k;
}
}
}
}
printf("%d\n",dp[1][n]); }
return 0;
}