我..莫名其妙搞出来的
随便搞搞..幻想中的dp结果对了
我也很迷茫
Description
为了研究农场的气候,Betsy帮助农夫John做了N(1 <= N <= 100)次气压测量并按顺序记录了结果M_1…M_N(1 <= M_i <= 1,000,000).
Betsy想找出一部分测量结果来总结整天的气压分布. 她想用K(1 <= K <= N)个数s_j(1 <= s_1 < s_2 < … < s_K <= N)来概括所有测量结果. 她想限制如下的误差:对于任何测量结果子集,每一个非此子集中的结果都会产生误差.总误差是所有测量结果的误差之和.更明确第说, 对于每一个和所有s_j都不同的i:
* 如果 i 小于 s_1, 误差是:2 * | M_i – M_(s_1) |
* 如果i在s_j和s_(j+1)之间,误差是:| 2 * M_i – Sum(s_j, s_(j+1)) | 注:Sum(x, y) = M_x + M_y; (M_x 和 M_y 之和)
* 如果i大于s_K,误差为:2 * | M_i – M_(s_K) |
Besty给了最大允许的误差E (1 <= E <= 1,000,000),找出最小的一部分结果使得误差最多为E.Input
第一行: 两个空格分离的数: N 和 E
第2..N+1行: 第i+1行包含一次测量记录:M_iOutput
第一行: 两个空格分开的数: 最少能达到误差小于等于E的测量数目 和 使用那个测量数目能达到的最小误差
Sample Input
4 20
10
320
40Sample Output
2 17
Hint
- 【样例说明】
选择第二和第四次测量结果能达到最小误差17. 第一次结果的误差是2*|10-3| = 14;第三次结果的误差是|2*20 – (3+40)|=3.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,e;
long long m[],ero[][],dp[][];//ero选i和j产生的误差//dp以j结尾的时候，有i个最少测量数目 能达到的最小误差
long long abss(long long a)
{
if(a<)return -a;
return a;
}
int main()
{
int i,j,k;
scanf("%d%d",&n,&e);
for(i=;i<=n;i++)scanf("%lld",&m[i]);
long long ans=n,anss=; for(k=;k<=n;k++)
{
for(i=k+;i<=n;i++)
for(j=k+;j<=i-;j++) /*枚举题中的i*/ ero[k][i]+=abss(*m[j]-m[i]-m[k]); for(i=;i<k;i++) ero[k][]+=*abss(m[i]-m[k]); //取k时，小于k的i值产生的误差
for(i=k+;i<=n;i++) ero[k][n+]+=*abss(m[i]-m[k]);// 取k时 大于k的i值产生的误差
}//关于误差 for(i=;i<=n;i++)
{
dp[][i]=ero[i][]+ero[i][n+];
if((dp[][i]<=e) && (dp[][i]<anss))
{
anss=dp[][i];ans=;
}
}//处理只取一个数的情况，也就是只取数i的情况 预处理 if(ans==){printf("%lld %lld\n",ans,anss);return ;}//如果可以只取一个数emm且满足条件啦 for(k=;k<=n;k++)//最少能达到误差小于等于E的测量数目
for(i=k;i<=n;i++)//枚举结尾的数
{
dp[k][i]=;
for(j=k-;j<i;j++)//枚举上一轮的结尾数
{
long long err=ero[j][i]+ero[i][n+]-ero[j][n+]; //相比上一轮多的误差
dp[k][i]=min(dp[k][i],dp[k-][j]+err);
}
if((dp[k][i]<=e) && (dp[k][i]<anss) && (k<=ans)) anss=dp[k][i],ans=k;//找最优解emm
}
printf("%lld %lld\n",ans,anss);
return ;
}
点击查看丑陋の代码&注释
