10.16动态规划专题解题报告

题目:problem

1.矩阵

真·水题

五分钟写完

代码:

// <matrix.cpp> – 10/16/15 08:19:03
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
int res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch = getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}
int n,m,s,w[401][401],v[401][401],dp[2][401][401],ans;
int main()
{
freopen(“matrix.in”,”r”,stdin);
freopen(“matrix.out”,”w”,stdout);
cin>>n>>m>>s;
for(int i=0;i<n;i++)
for(int o=0;o<m;o++)w[i][o]=getint();
for(int i=0;i<n;i++)
for(int o=0;o<m;o++)v[i][o]=getint();
if(w[0][0]<=s)dp[0][0][w[0][0]]=v[0][0];
for(int i=0;i<n;i++)
for(int o=0;o<m;o++)
for(int j=0;j<=s;j++){
if(i){
dp[i%2][o][j]=max(dp[i%2][o][j],dp[(i+1)%2][o][j]);
if(j+w[i][o]<=s)dp[i%2][o][j+w[i][o]]=max(dp[i%2][o][j+w[i][o]],dp[(i+1)%2][o][j]+v[i][o]);
}
if(o){
dp[i%2][o][j]=max(dp[i%2][o][j],dp[i%2][o-1][j]);
if(j+w[i][o]<=s)dp[i%2][o][j+w[i][o]]=max(dp[i%2][o][j+w[i][o]],dp[i%2][o-1][j]+v[i][o]);
}
}
for(int i=0;i<=s;i++)ans=max(ans,dp[(n-1)%2][m-1][i]);
cout<<ans;
return 0;
}

2.产品排序

打暴力

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz