SDUT《 算法分析与设计》 实验二-动态规划

SDUT《 算法分析与设计》 实验二-动态规划,第1张

SDUT《 算法分析与设计》 实验二-动态规划

动态规划
  • A - 高数Umaru系列(9)——哈士奇
  • B - 最少硬币问题
  • C - 数字三角形问题
  • D - 石子合并问题
  • E - 最长公共子序列问题

A - 高数Umaru系列(9)——哈士奇
#include 
#include 
#include
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair
#define x first
#define y second
#define PLL pair
#define PI acos(-1)
#define pb push_back
#define eb emplace_back
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 111;
int dx[]={-1, 0, 1, 0};
int dy[]={0, 1, 0, -1};
using namespace std;

int dp[N],v[N],w[N];

inline void solve(){
    int n,m;
    while(cin>>n>>m){
        mem(dp,0);
        for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
        for(int i=1;i<=n;i++){
            for(int j=m;j>=v[i];j--){
                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
            }
        }
        cout<>t;
    while(t--) solve();
    return 0;
}
B - 最少硬币问题
#include 
#include 
#include
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair
#define x first
#define y second
#define PLL pair
#define PI acos(-1)
#define pb push_back
#define eb emplace_back
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 111;
int dx[]={-1, 0, 1, 0};
int dy[]={0, 1, 0, -1};
using namespace std;

int dp[N],w[N],s[N];

inline void solve(){
    mem(dp,0x3f);
    int n; cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i]>>s[i];
    int m; cin>>m;
    dp[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=s[i];j++){
            for(int k=m;k>=w[i];k--){
                dp[k]=min(dp[k],dp[k-w[i]]+1);
            }
        }
    }
    if(dp[m]==inf) cout<<-1<>t;
    while(t--) solve();
    return 0;
}
C - 数字三角形问题
#include 
#include 
#include
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair
#define x first
#define y second
#define PLL pair
#define PI acos(-1)
#define pb push_back
#define eb emplace_back
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 111;
int dx[]={-1, 0, 1, 0};
int dy[]={0, 1, 0, -1};
using namespace std;

int dp[M][M];

inline void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>dp[i][j];
        }
    }
    for(int i=n-1;i>=1;i--){
        for(int j=1;j<=i;j++){
            dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]);
        }
    }
    cout<>t;
    while(t--) solve();
    return 0;
}
D - 石子合并问题
#include 
#include 
#include
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair
#define x first
#define y second
#define PLL pair
#define PI acos(-1)
#define pb push_back
#define eb emplace_back
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 211;
int dx[]={-1, 0, 1, 0};
int dy[]={0, 1, 0, -1};
using namespace std;

int a[M];
int sum[M];
int dp[M][M];
int mp[M][M];

inline void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];
    }
    mem(dp,0);
    mem(mp,0x3f);
    for(int i=1;i<=2*n;i++){
        sum[i]=sum[i-1]+a[i];
        mp[i][i]=mp[i+n][i+n]=0;
    }
    for(int len=1;len 
E - 最长公共子序列问题 
#include 
#include 
#include
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair
#define x first
#define y second
#define PLL pair
#define PI acos(-1)
#define pb push_back
#define eb emplace_back
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 511;
int dx[]={-1, 0, 1, 0};
int dy[]={0, 1, 0, -1};
using namespace std;

int dp[M][M];

inline void solve(){
    string a,b;
    cin>>a>>b;
    a=" "+a , b=" "+b;
    dp[0][0]=0;
    for(int i=1;i>t;
    while(t--) solve();
    return 0;
}

欢迎分享,转载请注明来源:内存溢出

原文地址:https://outofmemory.cn/zaji/5594005.html

(0)
打赏 微信扫一扫微信扫一扫 支付宝扫一扫支付宝扫一扫
上一篇 2022-12-15
下一篇2022-12-15

随机推荐

  • 婴儿进口奶粉_进口婴儿奶粉排行榜最新排名

    近几年,十大进口婴儿奶粉排名的名单中,总是能看到伊利金领冠睿护草饲婴幼儿配方奶粉。作为一款国产品牌旗下的进口奶粉,伊利金领冠睿护草饲奶粉用进口奶源和优质配方让妈妈们放心,成为最适合中国宝宝体质的“进口奶粉”。草饲奶粉是什么?可能对于有些新

    2022-12-29
    1800
  • 一般主卧双人床尺寸是多少

    导读:一般来说,主卧面积比较大,主人们都会选择摆放双人床,使得室内更加协调美观。不过双人床的尺寸有很多,大家可以根据卧室的面积,来挑选尺寸合适的主卧双人床。双人床尺寸通常有三种:1.5m×2m、1.8m×2m以及2m×2m。其中尺寸1.5m

  • 实木地板很多年了可以做翻新吗

    实木地板的装修成本还是很高的,不少人都在使用的时候会比较仔细,因为实木地板需要爱惜且维护。那么,实木地板很多年了可以做翻新吗?实木地板翻新可以换颜色吗?一起来看看学百科带来的详细介绍吧!实木地板很多年了可以做翻新吗实木地板可以翻新。但是翻新

    2022-12-29
    2100
  • 明胶是用什么做的 明胶哪种材质做的

    导读:明胶是用什么做的?下面为大家带来介绍。1、明胶是经胶原适度水解和热变性得到的产物,生产明胶的原料主要是动物的皮、骨及制革业废料等,市场上常见的明胶多以牛皮1、明胶是经胶原适度水解和热变性得到的产物,生产明胶的原料主要是动物的皮、骨及制

    2022-12-29
    1900
  • 承重梁开裂后如何加固

    导读:承重梁开裂是比较严重的房屋问题,会严重影响到居住的舒适性及安全,从而引发安全事故,那一般承重梁开裂后如何加固?下面一起来看看吧。当承重梁出现开裂后,可使用环氧树脂进行填补,接着在其表面粘一层贴碳纤维,这样能起到加固效果;也可以采取增大

    2022-12-29
    2000
  • 微星主板全核睿频_微星主板怎么样更新bios

    微星主板更新BIOS支持锐龙5000系列CPU现在锐龙5000系列的cpu已经上市了,可谓是真香,价格不高性能强悍,我就把原来的3600给换了,那是不是也得把主板换了呢?其实是不用的,毕竟换个主板实在是太麻烦了,不想拆螺丝了,而且都是A

    2022-12-29
    1900
  • 每逢佳节指的是什么节 每逢佳节是哪个节

    导读:每逢佳节指的是什么节?以下由小编为大家带来介绍。1、“每逢佳节倍思亲”中的佳节指的是重阳节。2、此句出自《九月九日忆山东兄弟》是唐代诗人王维创作的诗歌。该诗写出了游1、“每逢佳节倍思亲”中的佳节指的是重阳节。2、此句出自《九月九日忆山

  • 白米虾怎么保存才新鲜 白米虾如何保存才新鲜

    导读:白米虾怎么保存才新鲜?下面为大家带来介绍。1、新鲜白米虾保存的方法是用一块干净的纯棉毛巾浸透水后,拧干水待用,将淘洗干净的小虾均匀地滩在毛巾的一边,将放好小虾1、新鲜白米虾保存的方法是用一块干净的纯棉毛巾浸透水后,拧干水待用,将淘洗干

  • 适合送闺蜜杯子吗

    导读:1、闺蜜过生日是可以送水杯的,水杯的寓意是“一辈子”,送给闺蜜就代表,要和你做一辈子的好闺蜜、好朋友,送给闺蜜是很合适的礼物。2、杯子本身是用来盛水的,可以盛得满满当当1、闺蜜过生日是可以送水杯的,水杯的寓意是“一辈子”,送给闺蜜就代

    2022-12-29
    1400

发表评论

登录后才能评论

评论列表(0条)

    保存