2013
12-10

# Increasing Sequences

This is a problem from ZOJ 1499.To make it easyer,you just need output the last number.If there are leading zeros you should delete it.

Input will consist of multiple test cases. Each case will consist of one line, containing a string of digits of maximum length 80. A line consisting of a single 0 terminates input.

For each instance,output the last number.

3456
3546
3526
0001
100000101

6
46
26
1
101

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)

#include<cstdio>
#include<algorithm>
using namespace std;
#define min(x,y) (x)<(y)?(x):(y)
int a[2005];
int dp[2005][2005/2];
void work(int n,int k)
{
int i,j;
dp[0][0] = 0;//当取0件的时候所耗费的精力为0
for(i = 2; i <= n; i++)
{
dp[i][0] = 0;
for(j = 1; j <= i/2 ; j++)
if(i -1 >= j*2)//当i-1>= j*2的时候
dp[i][j] = min(dp[i-1][j],dp[i-2][j-1]+(a[i-1]-a[i])*(a[i-1]-a[i]));
else//当i-1< j*2的时候
dp[i][j] = dp[i-2][j-1] + (a[i-1]-a[i])*(a[i-1]-a[i]);
}
printf("%d\n",dp[n][k]);//输出最小的疲劳度。
}
int main()
{
int n,k,i;
while(~scanf("%d%d",&n,&k))
{
for(i = 1; i <= n; i++)//输入数据，输入从1开始。
scanf("%d",a+i);
sort(a+1,a+n+1);//将元素从小到大进行排序。
work(n,k);
}
return 0;
}

1. 代码是给出了，但是解析的也太不清晰了吧！如 13 abejkcfghid jkebfghicda
第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3)，为什么要这样拆分，原则是什么？