- A - 高数Umaru系列(9)——哈士奇
- B - 最少硬币问题
- C - 数字三角形问题
- D - 石子合并问题
- E - 最长公共子序列问题
#includeB - 最少硬币问题#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; }
#includeC - 数字三角形问题#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; }
#includeD - 石子合并问题#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; }
#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; } 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)