Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
149129 | 韩立鹏 | 切割铜棒 | C++ | 通过 | 100 | 3 MS | 4164 KB | 612 | 2024-05-25 16:34:54 |
#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) //k分成两部分 dp[s][s+i]=min(dp[s][s+i],dp[s][k]+dp[k][s+i]+cut[s+i]-cut[s]); cout<<"The minimum cutting is "<<dp[0][N+1]<< "."<<endl; } return 0; }