健康饮食网站设计论文,做asp网站需要的实验报告单,wordpress瀑布流主题怎么设置首页显示文章数量,江门整站优化维修栅栏
题目大意#xff1a;
有一串数#xff0c;要把这一串数改成全部非0的#xff0c;每一次可以更改某一段的全部数字#xff0c;但有代价sqrt(m)sqrt(m)sqrt(m)#xff08;m为当前子串的长度#xff09;
原题#xff1a;
题目描述
农场的栅栏年久失修#x…维修栅栏
题目大意
有一串数要把这一串数改成全部非0的每一次可以更改某一段的全部数字但有代价sqrt(m)sqrt(m)sqrt(m)m为当前子串的长度
原题
题目描述
农场的栅栏年久失修出现了多处破损晶晶准备维修它栅栏是由n块木板组成的每块木板可能已经损坏也可能没有损坏。晶晶知道维修连续m个木板这m个木板不一定都是损坏的的费用是sqrt(m。可是怎样设计方案才能使总费用最低呢请你写程序帮忙计算。
输入
第一行包含一个整数n(n2500)表示栅栏的长度。 第二行包含n个由空格分开的整数(-1000~1000)如果第i个数是0则表示第i块木板已经损坏否则表示没损坏。
输出
一个实数表示最小维修费用。 注意答案精确到小数点后3位。
输入样例
9
0 -1 0 1 2 3 0 -2 0输出样例
3.000解题思路
直接DP枚举每一次的子串如果子串内有0那修否则不修
代码
#includecmath
#includecstdio
#includecstring
#includeiostream
#define ld long double
using namespace std;
int n,x,b[3000];
ld f[3000];
ld minn(ld aa,ld bb)
{if (aabb) return aa;return bb;
}
int main()
{scanf(%d,n);for (int i1;in;i){scanf(%d,x);if (!x) b[i];b[i]b[i-1];//前缀和}memset(f,0x7f,sizeof(f));f[0]0;for (int i1;in;i){for (int j0;ji;j)if (b[i]b[j]) f[i]minn(f[i],f[j]);//判断有没有0没有直接赋值else f[i]minn(f[i],f[j]sqrt((ld)(i-j)));//有则全部改变}printf(%.3Lf,f[n]);return 0;
}
