XP03-B Day6 代码默写答案
2026-08-07 20:51:23
发布于：广东
17阅读
0回复
0点赞
代码默写答案
第一题
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int dp[N],w[N],v[N];
void solve(){
int n,V;
cin>>n>>V;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];
}
for(int i=1;i<=n;i++){
for(int j=V;j>=w[i];j--){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[V];
}
signed main(){
std::ios::sync_with_stdio(false);
cout.tie(0);cin.tie(0);
int _=1;
// cin>>_;
while(_--){
solve();
}
}
第二题
#include<bits/stdc++.h>
#include <bitset>
#define int long long
using namespace std;
const int N=1e5+10;
int dp[N];
int v[N],w[N];
void solve(){
int n,sum=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>v[i];
sum+=v[i];
}
dp[0]=1;
if(sum%2==1){
cout<<"NO\n";
return;
}
for(int i=1;i<=sum;i++)dp[i]=0;
for(int i=1;i<=n;i++){
for(int j=sum;j>=v[i];j--){
dp[j]=dp[j]|dp[j-v[i]];
}
}
cout<<(dp[sum/2]==1?"YES":"NO")<<"\n";
}
signed main(){
int _=1;
cin>>_;
while(_--){
solve();
}
}
第三题
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+10;
int dp[N][N],v[N],w[N],m[N];
void solve(){
int n,M,V;
cin>>n>>V>>M;
for(int i=1;i<=n;i++){
cin>>v[i]>>m[i]>>w[i];
}
// dp[0]=1;
for(int i=1;i<=n;i++){
for(int j=V;j>=v[i];j--){
for(int k=M;k>=m[i];k--)
dp[j][k]=max(dp[j][k],dp[j-v[i]][k-m[i]]+w[i]);
}
}
cout<<dp[V][M]<<"\n";
}
signed main(){
int _=1;
// cin>>_;
while(_--){
solve();
}
}
第四题
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int dp[N],w[N],v[N];
void solve(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];
}
for(int i=1;i<=n;i++){
for(int j=w[i];j<=m;j++){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[m];
}
signed main(){
int _=1;
// cin>>_;
while(_--){
solve();
}
}
第五题
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int dp[N],w[N],v[N],c[N];
void solve(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i]>>c[i];
}
for(int i=1;i<=n;i++){
for(int k=1;k<=c[i];k++){
for(int j=m;j>=w[i];j--){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
}
cout<<dp[m];
}
signed main(){
int _=1;
// cin>>_;
while(_--){
solve();
}
}
第六题
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+10;
int dp[N][N],sum[N],a[N],v[N],w[N],m[N];
void init(int n){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dp[i][j]=1e9;
}
}
}
void solve(){
int n;
cin>>n;
init(n);
for(int i=1;i<=n;i++){
cin>>a[i];
sum[i]=sum[i-1]+a[i];
dp[i][i]=0;
}
for(int len=2;len<=n;len++){
for(int l=1;l+len-1<=n;l++){
int r=l+len-1;
for(int k=l;k<r;k++){
int val=sum[r]-sum[l-1];
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+val);
}
}
}
// cout<<dp[1][2]<<" ";
cout<<dp[1][n]<<"\n";
}
signed main(){
int _=1;
// cin>>_;
while(_--){
solve();
}
}
第七题
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+10;
int dis[N][N],st[N][N];
string mp[N];
int dx[]={0,1,-1,0};
int dy[]={1,0,0,-1};
int n,m;
struct point{
int x,y;
};
void bfs(int sx,int sy){
deque<point>q;
dis[sx][sy]=0;
q.push_back({sx,sy});
while(q.size()!=0){
point p=q.front();
q.pop_front();
// if(mp[p.x][p.y]=='T')
for(int i=0;i<4;i++){
int x=p.x+dx[i];
int y=p.y+dy[i];
if(x<=n&&x>=1&&y>=1&&y<=m&&dis[x][y]==1e9){
if(mp[x][y]=='#'){
q.push_back({x,y});
dis[x][y]=dis[p.x][p.y]+1;
}
else {
q.push_front({x,y});
dis[x][y]=dis[p.x][p.y];
}
}
}
}
}
void solve(){
cin>>n>>m;
int sx,sy,ex,ey;
queue<point>q;
for(int i=1;i<=n;i++){
cin>>mp[i];
mp[i]=" "+mp[i];
for(int j=1;j<=m;j++){
if(mp[i][j]=='S')sx=i,sy=j;
else if(mp[i][j]=='T')ex=i,ey=j;
dis[i][j]=1e9;
}
}
bfs(sx,sy);
cout<<dis[ex][ey]<<"\n";
}
signed main(){
int _=1;
// cin>>_;
while(_--){
solve();
}
}
这里空空如也
有帮助，赞一个