Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
153481 陈家宝 切割铜棒 C++ 通过 100 4 MS 4160 KB 536 2024-07-03 13:30:32

Tests(5/5):


#include<bits/stdc++.h> using namespace std; int L,N,cut[1000],dp[1000][1000]; int main(){ while(cin>>L>>N){ if(L==0)break; for(int i=1;i<=N;++i)cin>>cut[i]; cut[0]=0; cut[N+1]=L; memset(dp,127/2,sizeof(dp)); for(int i=0;i<=N;++i)dp[i][i+1]=0; for(int i=2;i<=N+1;++i)for(int s=0;s+i<=N+1;++s)for(int k=s+1;k<s+i;++k)dp[s][s+i]=min(dp[s][s+i],dp[s][k]+dp[k][s+i]+cut[s+i]-cut[s]);//枚举跨度;枚举起始点;k分成两部分 cout<<"The minimum cutting is "<<dp[0][N+1]<<"."<<endl; } return 0; }


测评信息: