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

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