每日算法 – day 23

每日算法

those times when you get up early and you work hard; those times when you stay up late and you work hard; those times when don’t feel like working — you’re too tired, you don’t want to push yourself — but you do it anyway. That is actually the dream. That’s the dream. It’s not the destination, it’s the journey. And if you guys can understand that, what you’ll see happen is that you won’t accomplish your dreams, your dreams won’t come true, something greater will. mamba out

那些你早出晚归付出的刻苦努力，你不想训练，当你觉的太累了但还是要咬牙坚持的时候，那就是在追逐梦想，不要在意终点有什么，要享受路途的过程，或许你不能成就梦想，但一定会有更伟大的事情随之而来。 mamba out~

2020.3.7-3.8

lqb 字符串顺序比较

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int cmp(string a,string b)
{
    if(a == b)return 0;
    else if(a < b)return 1;
    else return -1;
}
int main()
{
    string a, b ;
    getline(cin,a);
    getline(cin,b);
    cout << cmp(a, b ) << endl;
    return 0;
}

lqb 圆的周长和面积

#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <istream>
#include <sstream>
#include <fstream>

using namespace std;
const double pa = 3.14;

string tostring(double a)
{
    stringstream s;
    s << a;
    return s.str(); 
}
int main()
{

    double r;
    cin >> r;

    double s = pa * 2 * r;
    double v = pa * r * r;

    string ss = tostring(s);
    string vv = tostring(v);

    cout << ss << endl << vv;
    return 0;
} 

猴子吃桃问题

递归

#include <iostream>
#include <cstdio>

using namespace std;
int n;
int GetNumber(int n)
{

    if(n == 1){
        return 1;
    }
    else{
        return 2 *  GetNumber(n - 1) + 2;
    }   
}
int main()
{
    cin >> n;
    cout << GetNumber(n) ;
}

luogu -P2347 砝码称重

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int a[10010],x,num,b[10]={0,1,2,3,5,10,20},ans;
bool t[10010];
int main()
{
    for(int i=1;i<=6;i++)
    {
        cin >> x;
        for(int j = 1;j <= x; j++)  a[++num] = b[i];  //在a数组里记录所有砝码重 
    }
    t[0] = 1;
    for(int i = 1;i <= num ;i ++)
    {
        for(int j = 1010 ;j >= 0;j --) // 倒着枚举是关键 
        {
            if(t[j]) t[j + a[i]] = 1;
        }
    }
    for(int i = 1;i <= 1010 ;i ++)
    {
        if(t[i])ans++;
    }
    printf("Total=%d",ans);
    return 0;
}

luogu -P1048 采药dp

#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>

using namespace std;
const int N = 1500;
int t , m; // t 是时间限制， m 是草药数量 
int dp[N][N];
int w[N] , v[N]; // 采这一株草药所花得时间得和其价值 

int main()
{
    cin >> t >> m;

    for(int i = 1;i <= m ;i ++)
    {
        cin >> w[i] >> v[i]; 
    }

    /*
      如果我们想要让最终能得到得背包价值容量最大

    */
    for(int i = 1;i <= m;i ++)
    {
        for(int j = t;j >= 0 ;j --)
        {
            if(j >= w[i])
            {
                dp[i][j] = max(dp[i-1][j-w[i]] + v[i],dp[i-1][j]);
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }   
    } 
    cout << dp[m][t] ;
    return 0;
} 

luogu -P1048 采药 -记忆化搜索

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;
const int N = 1500;
int cost[N], v[N] , n , t;
int f[N][N];
// 对于每一个状态我们都有选择或者不选两种情况
// 参数 1. 当前选择了几个物品 2. 剩余时间 3. 当前价值 

int ans = 0;
int dfs(int now,int time)
{
    if(f[now][time] != -1)return f[now][time];
    if(now == n + 1)
    {
        return f[now][time] = 0;
    }
    int dfs1 , dfs2 = -9999;
    dfs1 = dfs(now + 1,time); // 不选

    if(time >= cost[now])
    {
        dfs2 = dfs(now + 1,time - cost[now]) + v[now];
    } 
    return f[now][time] = max(dfs1,dfs2);
} 
int main()
{
    cin >> t >> n;
    for(int i = 1;i <= n ;i ++)
    {
        cin >> cost[i] >> v[i];
    }
    fill(f[0],f[0] + N * N , -1);
    cout << dfs(1,t); 

    return 0;
}