Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cmath>
#define sqr(x) ((x)*(x))
using namespace std;
const double PI = 3.141592654;

int n, m, len[10010], type[10010];
double f[10010][22];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> type[i];
    for (int i = 1; i <= n; i++) cin >> len[i];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = 1e18;
            if (!type[i])
            {
                for (int jj = 1; jj <= m; jj++)
                    if (abs(j - jj) * 100 <= len[i])
                        f[i][j] = min(f[i][j], f[i - 1][jj] + sqrt(sqr(len[i]) + sqr((j - jj) * 10)));
            }
            else
            {
                double radius = len[i] + 5;
                if (type[i] == 1) radius += 10 * (j - 1);
                else radius += 10 * (m - j);
                f[i][j] = f[i - 1][j] + radius * PI * 0.5;
            }
        }

    double ans = 1e18;
    for (int j = 1; j <= m; j++) ans = min(ans, f[n][j]);
    printf("%.2lf\n", ans);
}

Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 10005
#define M 25
#define sqr(x) ((x)*(x))

int l[N], n, m;
double f[N][M], s[N];

int main() {
#ifndef ONLINE_JUDGE
    freopen( "input.txt", "r", stdin );
    freopen( "output.txt", "w", stdout );
#endif
    scanf("%d%d",&n,&m);
    fo(i,1,n) scanf("%d",l+i);
    fo(i,1,n) scanf("%lf",s+i);
    fo(i,1,n) fo(j,1,m) switch(l[i]){
        case 2: f[i][j] = f[i-1][j] + (10*j-5+s[i])*M_PI/2; break;
        case 1: f[i][j] = f[i-1][j] + (10*(m-j)+5+s[i])*M_PI/2; break;
        default:
            f[i][j] = DBL_MAX;
            fo(k,max(1,j-(int)(s[i]/100)),min(m,j+(int)(s[i]/100)))
                f[i][j] = min(f[i][j],f[i-1][k]+sqrt(sqr(s[i])+100*sqr(j-k)));
    }
    double res = DBL_MAX;
    fo(i,1,m) res = min(res, f[n][i]);
    printf("%.2lf\n", res);
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
#define REP(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)

const double INF = 1e9;
const double PI = 3.141592654;
const int N = 10101;
const int M = 22;

using namespace std;

void minimize(double &a, double b)
  { a = a > b ? b : a; }

double getLengthLine(int a, int b)
  { return sqrt(a * a + b * b); }

double getLengthCurve(int radius)
  { return PI * radius / 2; }

int n, m;
int type[N], s[N];
double dp[2][M];

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  #ifdef _LAD_
    freopen("SDRIVE.in", "r", stdin);
  #endif // _LAD_
  cin >> n >> m;
  REP(i, 1, n) cin >> type[i];
  REP(i, 1, n) cin >> s[i];
  int now = 0, nxt = 1;
  REP(i, 1, n) {
    REP(j, 1, m)
      dp[nxt][j] = INF;
    REP(j, 1, m) {
      if (type[i] == 0) {
        int range = s[i] / 100;
        REP(k, max(1, j - range), min(m, j + range))
          minimize(dp[nxt][k], dp[now][j] + getLengthLine(s[i], abs(j - k) * 10));
      } else if (type[i] == 1) {
        minimize(dp[nxt][j], dp[now][j] + getLengthCurve(s[i] + (j - 1) * 10 + 5));
      } else {
        minimize(dp[nxt][j], dp[now][j] + getLengthCurve(s[i] + (m - j) * 10 + 5));
      }
    }
    now ^= 1; nxt ^= 1;
  }
  double ans = INF;
  REP(i, 1, m)
    minimize(ans, dp[now][i]);
  cout << setprecision(2) << fixed << ans << endl;
  return 0;
}

Code mẫu của RR

#include <iomanip>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>

#define FOR(i,a,b) for(int i=(a),_b=(b); i <= _b; ++i)
#define FORD(i,a,b) for(int i=(a),_b=(b); i >= _b; --i)
#define REP(i,a) for(int i=0,_a=(a); i < _a; ++i)
using namespace std;

long double f[10111][22];
int n, m;
int type[10111], s[10111];

#define sqr(x) ((x) * (x))

int main() {
    cout << (fixed) << setprecision(10);
    while (scanf("%d%d", &n, &m) == 2) {
        FOR(i,1,n) scanf("%d", &type[i]);
        FOR(i,1,n) scanf("%d", &s[i]);

        FOR(i,1,n) FOR(j,1,m) f[i][j] = 1e50;
        FOR(j,1,m) f[0][j] = 0;

        FOR(i,0,n-1) FOR(j,1,m) {
            if (type[i+1] == 0) {
                FOR(jj,1,m)
                if (abs(j - jj) * 100 <= s[i+1]) {
                    f[i+1][jj] = min(f[i+1][jj], 
                        f[i][j] + sqrt(sqr((j - jj)*10.0) + sqr(s[i+1])));
                }
            }
            else {
                long double r = s[i+1];
                if (type[i+1] == 1) r += (j - 0.5) * 10.0;
                else r += (m - j + 0.5) * 10;

                f[i+1][j] = min(f[i+1][j], f[i][j] + 3.141592654 * r / 2.0);
            }
        }
        long double res = 1e50;
        FOR(j,1,m) res = min(res, f[n][j]);

        cout << res << endl;
    }
    return 0;
}

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>
#include <cassert>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int i = (a); i >= (b); --i)
#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
//#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }

const int bfsz = 1 << 16;
char bf[bfsz + 5];
int rsz = 0;
int ptr = 0;
char gc() {
    if (rsz <= 0) {
        ptr = 0;
        rsz = (int) fread(bf, 1, bfsz, stdin);
        if (rsz <= 0)
            return EOF;
    }
    --rsz;
    return bf[ptr++];
}
void ga(char &c) {
    c = EOF;
    while (!isalpha(c))
        c = gc();
}
int gs(char s[]) {
    int l = 0;
    char c = gc();
    while (isspace(c))
        c = gc();
    while (c != EOF && !isspace(c)) {
        s[l++] = c;
        c = gc();
    }
    s[l] = '\0';
    return l;
}
template<class T> bool gi(T &v) {
    v = 0;
    char c = gc();
    while (c != EOF && c != '-' && !isdigit(c))
        c = gc();
    if (c == EOF)
        return false;
    bool neg = c == '-';
    if (neg)
        c = gc();
    while (isdigit(c)) {
        v = v * 10 + c - '0';
        c = gc();
    }
    if (neg)
        v = -v;
    return true;
}

typedef pair<int, int> II;

const ld PI = acos(-1.0);
const ld eps = 1e-9;

const int dr[] = {+1, +0, +0, -1};
const int dc[] = {+0, +1, -1, +0};

const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
//const ll mod = (ll)1e9 + 7;

#define maxn 20005

int n, m, id[maxn];
ld f[maxn][22], d[maxn];

int main(){
//    freopen("in.txt", "r", stdin);
    cin >> n >> m;
    For(i, 1, n) cin >> id[i];
    For(i, 1, n) cin >> d[i];

    For(i, 1, n) For(j, 1, m) f[i][j] = linf;
    For(i, 1, m) f[0][i] = 0;

    For(i, 1, n){
        if(id[i] == 2){
            For(j, 1, m){
                ld r = d[i] + 5.0 * (j + j - 1);
                f[i][j] = f[i - 1][j] + r * PI / 2;
            }
        }
        else if(id[i] == 1){
            For(j, 1, m){
                ld r = d[i] + 5.0 * (m + m - j - j + 1);
                f[i][j] = f[i - 1][j] + r * PI / 2;
            }
        }
        else{
            int num = (int)((d[i] + 0.5) / 100);
            For(j, 1, m){
                For(k, max(1, j - num), min(m, j + num)){
                    ld r = 10.0 * abs(j - k);
                    ld dis = sqrt(r * r + d[i] * d[i]);
                    f[i][k] = min(f[i][k], f[i - 1][j] + dis);
                }
            }
        }
    }

    ld res = linf;
    For(i, 1, m) res = min(res, f[n][i]);
    cout << fixed << setprecision(2) << res;
}

Code mẫu của skyvn97

#include<stdio.h>
#include<math.h>
#define PI   acos(-1.0)
#define INF   1e9
double f[10101][22];
int s[10101];
int l[10101];
int n,m;
void init(void) {
    int i;
    scanf("%d",&n);
    scanf("%d",&m);
    for (i=1;i<=n;i=i+1) scanf("%d",&l[i]);
    for (i=1;i<=n;i=i+1) scanf("%d",&s[i]);
}
int abs(int x) {
    if (x<0) return (-x); else return (x);
}
double min(double a,double b) {
    if (a<b) return (a); else return (b);
}
void optimize(void) {
    int i,j,k;
    for (i=1;i<=m;i=i+1) f[0][i]=0;
    for (i=1;i<=n;i=i+1)
        for (j=1;j<=m;j=j+1) {
            if (l[i]==0) {
                f[i][j]=INF;
                for (k=1;k<=m;k=k+1)    
                    if (abs(j-k)*100<=s[i])
                        f[i][j]=min(f[i][j],f[i-1][k]+hypot((j-k)*10,s[i]));
            }
            if (l[i]==1) f[i][j]=f[i-1][j]+PI*(s[i]+j*10-5)/2;
            if (l[i]==2) f[i][j]=f[i-1][j]+PI*(s[i]+5+10*m-10*j)/2;
        }
    double r=INF;
    for (i=1;i<=m;i=i+1)
        if (f[n][i]<r) r=f[n][i];
    printf("%.2lf",r);
}
int main(void) {
    init();
    optimize();
}