建学校pascal
用dp做应该可以,实在不行用深搜、穷举(虽然不能满分)。穷举思路:做全排列。然后每遍搜索出最小值。应该可以优化,剪枝好的话满分没问题。程序很简单。但时间复杂度非优化为O(n平方),你的数据完全可以过。 动态规划思想:因为是100,所以就可以用n^3的方法。那么怎么定义数组,又怎么写方程式呢?思路1: f[i][j][k],i表示当前算到的村庄,j表示上一所学校的位置且iusing namespace std;int main(){ long n,l,i,j,k,p,stu[101],beh[101][101],aft[101][101],f[101][11],dis[101][101],...全部
用dp做应该可以,实在不行用深搜、穷举(虽然不能满分)。穷举思路:做全排列。然后每遍搜索出最小值。应该可以优化,剪枝好的话满分没问题。程序很简单。但时间复杂度非优化为O(n平方),你的数据完全可以过。
动态规划思想:因为是100,所以就可以用n^3的方法。那么怎么定义数组,又怎么写方程式呢?思路1: f[i][j][k],i表示当前算到的村庄,j表示上一所学校的位置且iusing namespace std;int main(){ long n,l,i,j,k,p,stu[101],beh[101][101],aft[101][101],f[101][11],dis[101][101],d,leas; freopen("school。
in","r",stdin); freopen("school。
out","w",stdout);//文件 cin>>n>>l; for (i=1;i>stu[i]; memset(dis,0,sizeof dis); memset(beh,0,sizeof beh); memset(aft,0,sizeof aft); memset(f,1,sizeof f);//赋大值 for (i=1;i>d;//读入并处理dis dis[i][i 1]=d; dis[1][i 1]=dis[i][i 1] dis[1][i]; for (j=1;j=1;j--) aft[j][i]=aft[j 1][i] dis[j][i]*stu[j]; }//二维预处理aft与beh f[1][1]=0;//初值 for (i=2;i { f[i][1]=aft[1][i];//1所学校要特殊处理 for (j=1;j for (k=2;k for (p=j;p if (f[j][k-1] beh[j][p] aft[p 1][i] f[i][k]=f[j][k-1] beh[j][p] aft[p 1][i]; } leas=2147483647; for (i=2;i if (f[i][l] beh[i][n] cout}打了半天代码,望采纳!。收起