最小花费爬楼梯

C++ 解法, 执行用时: 6ms, 内存消耗: 1168KB, 提交时间: 2022-03-04

#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &f)
{
    f=0;T fu=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-'){fu=-1;}c=getchar();}
    while(c>='0'&&c<='9') {f=(f<<3)+(f<<1)+(c&15);c=getchar();}
    f*=fu;
}
template <typename T>
void print(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+48);
    else print(x/10),putchar(x%10+48);
}
template <typename T>
void print(T x, char t)
{
    print(x);putchar(t);
}
const int maxn=1e5+50;
int n,a[maxn];
int dp[maxn];
void solve()
{
    read(n);
    for(int i=1;i<=n;++i) 
    read(a[i]);
    dp[1]=dp[2]=0;
    for(int i=3;i<=n+1;++i)
    {
        dp[i]=min(dp[i-1]+a[i-1],dp[i-2]+a[i-2]);
    }
    print(dp[n+1]);
}
int main()
{
    #ifdef AC
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    clock_t program_start_clock=clock();
    solve();
    fprintf(stderr,"\nTotal Time: %lf ms",double(clock()-program_start_clock)/(CLOCKS_PER_SEC/1000));
    return 0;
}

C++ 解法, 执行用时: 6ms, 内存消耗: 1180KB, 提交时间: 2022-05-08

#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T& f) {
    f = 0;
    T fu = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') {
            fu = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        f = (f << 3) + (f << 1) + (c & 15);
        c = getchar();
    }
    f *= fu;
}
template <typename T>
void print(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x < 10) putchar(x + 48);
    else print(x / 10), putchar(x % 10 + 48);
}
template <typename T>
void print(T x, char t) {
    print(x);
    putchar(t);
}
const int maxn = 1e5 + 50;
int n, a[maxn];
int dp[maxn];
void solve() {
    read(n);
    for (int i = 1; i <= n; ++i)
        read(a[i]);
    dp[1] = dp[2] = 0;
    for (int i = 3; i <= n + 1; ++i) {
        dp[i] = min(dp[i - 1] + a[i - 1], dp[i - 2] + a[i - 2]);
    }
    print(dp[n + 1]);
}
int main() {
#ifdef AC
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    clock_t program_start_clock = clock();
    solve();
    fprintf(stderr, "\nTotal Time: %lf ms",
            double(clock() - program_start_clock) / (CLOCKS_PER_SEC / 1000));
    return 0;
}

C 解法, 执行用时: 10ms, 内存消耗: 1076KB, 提交时间: 2022-02-15

#include <stdio.h>
#include <stdlib.h>

int Min(int i,int j){
    return i>j?j:i;
}

int main(){
    int n =0;
    scanf("%d",&n);
    int *dp,*cost;
    dp = (int*)malloc(sizeof(int)*n);
    cost = (int*)malloc(sizeof(int)*n);
    for(int i=0;i<n;i++){
        scanf("%d",cost+i);
        dp[i] =0;
    }
    //初始化
    if(n==1){
        printf("%d",cost[0]);
    }else if(n==2){
        printf("%d",Min(cost[0],cost[1]));
    }else{
        dp[n-1] = cost[n-1];
        dp[n-2] = cost[n-2];
        for(int i =n-3;i>=0;i--){
            dp[i] = cost[i]+Min(dp[i+1],dp[i+2]);
//             min_cost = Min(min_cost, dp[i]);
        }
        printf("%d",Min(dp[0], dp[1]));
    }
    
    return 0;
}

C 解法, 执行用时: 11ms, 内存消耗: 316KB, 提交时间: 2022-03-28

#include <stdio.h>
#include <assert.h>
int main(void)
{
    int n;
    while(scanf("%d", &n) != EOF)
    {
        assert(n>0 && n<=100000);
        if(n < 3){
            int val_0;   scanf("%d", &val_0);   assert(val_0>0 && val_0<=10000);
            if(n < 2){ printf("%d\n", val_0);   continue; }
            int val_1;   scanf("%d", &val_1);   assert(val_1>0 && val_1<=10000);
            printf("%d\n", val_0<val_1 ? val_0 : val_1);   continue;
        }
        
        int val_0, val_1;
        scanf("%d %d", &val_0, &val_1);
        assert(val_0>0 && val_0<=10000);   assert(val_1>0 && val_1<=10000);
        
        int dp_0 = 0, dp_1 = 0;
        for(int i=2,val; i<n; ++i){
            int tmp_0 = dp_0+val_0, tmp_1 = dp_1+val_1;
            dp_0 = dp_1;   dp_1 = tmp_0<tmp_1 ? tmp_0 : tmp_1;
            val_0 = val_1;   scanf("%d", &val_1);   assert(val_1>0 && val_1<=10000);
        }
        int tmp_0 = dp_0+val_0, tmp_1 = dp_1+val_1;
        printf("%d\n", tmp_0<tmp_1 ? tmp_0 : tmp_1);
    }
    return 0;
}

C++ 解法, 执行用时: 11ms, 内存消耗: 1164KB, 提交时间: 2022-03-27

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
int cost[100000],dp[100001];
int main(){
    IOS;
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>cost[i];
    for(int i=2;i<=n;i++)
        dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
    cout<<dp[n];
    return 0;
}

详情