codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include<cstdio> #include<iostream> #include<vector> #include<map> #include<stack> #include<queue> #include<bitset> #include<list> #include<iomanip> #include<string> #include<climits> #include <sstream> #include <fstream> #include<cctype> #include<time.h> #include<assert.h> #include <numeric> #include <functional> #include<cstring> #include<cmath> #include<iterator> #include <memory.h> #include<utility> #include <ctime> #include<algorithm> #define all(v) v.begin(),v.end() #define read(a) freopen("a.txt","r",stdin) #define write(b) freopen("b.txt","w",stdout) #define min3(a,b,c) min(a,min(b,c)) #define max3(a,b,c) max(a,max(b,c)) #define min4(a,b,c,d) min(min(a,b),min(c,d)) #define max4(a,b,c,d) max(max(a,b),max(c,d)) #define maxall(v) *max_element(all(v)) #define minall(v) *min_element(all(v)) #define pb push_back #define mk make_pair #define SORT(v) sort(all(v)) #define UN(v) SORT(v), (v).earse(unique(all(v)),v.end()) #define common(a,b) SORT(a), SORT(b), a.erase(set_intersection(all(a),all(b),a.begin()),a.end()) #define uncommon(a,b) SORT(a), SORT(b), a.erase(set_symmetric_difference(all(a),all(b),a.begin()),a.end()) #define FILL(a,d) memset(a,d,sizeof(a)) #define LL long long #define PI 2*acos(0.0) #define pi pair<int,int> using namespace std; const int inf=1000000007; int a[1005]; int dp[100][100]; int f(int start,int end) { if(dp[start][end]!=-1) return dp[start][end]; if(end-start==1) return dp[start][end]=0; int mincost=inf; for(int i=start+1;i<end;i++) { int cost=(a[end]-a[start])+f(start,i)+f(i,end); mincost=min(cost,mincost); } dp[start][end]=mincost; return dp[start][end]; } int main() { int i,j,k,n,d,l; while(cin>>l) { if(l==0) break; FILL(dp,-1); cin>>n; a[0]=0; for(i=1;i<=n;i++) cin>>a[i]; a[n+1]=l; cout<<"The minimum cutting is "<<f(0,n+1)<<"."<<endl; } return 0; }
Private
[
?
]
Run code
Submit