HDU1024
https://blog.csdn.net/pmt123456/article/details/52695470?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-1.base&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-1.base
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<iomanip>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<list>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>0&&x<=n&&y>0&&y<=m)
//#include<bits/stdc++.h>
using namespace std;
const ll maxx=1e9;
const int inf=0x7ffffff;
int dir[7][4]={
{1,0},
{0,-1},
{0,1},
{-1,0}
};
int n,m,dp[1000005],a[1000005],pre[1000005];
void solve(){
}
int main(){
// freopen("in.txt","r",stdin);
while(scanf("%d%d",&m,&n)!=EOF){
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
memset(dp,0,sizeof dp);
memset(pre,0,sizeof pre);
int temp;
for(int i=1;i<=m;i++){
temp=-inf;//要开到最小值，不然会wa
for(int j=i;j<=n;j++){
dp[j]=max(dp[j-1],pre[j-1])+a[j];
pre[j-1]=temp;
temp=max(temp,dp[j]);
}
}
printf("%d\n",temp);
}
return 0;
}
HDU2602
??????? 打印路径的一种方法（自己想的，感觉应该对。。。）
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<iomanip>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<list>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>0&&x<=n&&y>0&&y<=m)
//#include<bits/stdc++.h>
using namespace std;
const ll maxx=1e9;
int dir[7][4]={
{1,0},
{0,-1},
{0,1},
{-1,0}
};
struct bone{
int cap,val;
}a[1005];
int dp[1005][1005]={0},n,v,path[1000][1000];
void solve(){
memset(dp,0,sizeof dp);
memset(path,0,sizeof path);
for(int i=1;i<=n;i++){
for(int j=0;j<=v;j++){
if(a[i].cap>j)
dp[i][j]=dp[i-1][j];
else{
if(dp[i-1][j]>=dp[i-1][j-a[i].cap]+a[i].val)
dp[i][j]=dp[i-1][j];
else{
dp[i][j]=dp[i-1][j-a[i].cap]+a[i].val;
path[i][j]=i;
}
}
}
}
}
void print(int n,int v){
while(n&&v){
cout<<path[n][v]<<" ";
int tmp=path[n][v];
n--;
v-=a[tmp].cap;
}
}
int main(){
freopen("in.txt","r",stdin);
int t;
cin>>t;
while(t--){
cin>>n>>v;
for(int i=1;i<=n;i++) cin>>a[i].val;
for(int i=1;i<=n;i++) cin>>a[i].cap;
solve();
cout<<dp[n][v]<<endl;
print(n,v);
}
return 0;
}
最长公共子序列
//最简单的打法加输出子序列
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<iomanip>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<list>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>0&&x<=n&&y>0&&y<=m)
//#include<bits/stdc++.h>
using namespace std;
const ll maxx=1e9;
int dir[7][4]={
{1,0},
{0,-1},
{0,1},
{-1,0}
};
string s1,s2;
int dp[1000][1000],b[1000][1000];
void solve(){
memset(dp,0,sizeof dp);
for(int i=1;i<=s1.size();i++){
for(int j=1;j<=s2.size();j++){
if(s1[i-1]==s2[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
b[i][j]=1;
}
else{
if(dp[i-1][j]>=dp[i-1][j]){
dp[i][j]=dp[i-1][j];
b[i][j]=2;
}
if(dp[i-1][j]<dp[i][j-1]){
dp[i][j]=dp[i][j-1];
b[i][j]=3;
}
}
}
}
cout<<dp[s1.size()][s2.size()]<<endl;
}
void print(int i,int j){
if(i==0||j==0) return;
if(b[i][j]==1){
print(i-1,j-1);
cout<<s1[i-1];
}
if(b[i][j]==2) print(i-1,j);
if(b[i][j]==3) print(i,j-1);
}
int main(){
freopen("in.txt","r",stdin);
while(cin>>s1>>s2){
solve();
print(s1.size(),s2.size());
cout<<endl;
}
return 0;
}
//滚动数组
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<iomanip>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<list>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>0&&x<=n&&y>0&&y<=m)
//#include<bits/stdc++.h>
using namespace std;
const ll maxx=1e9;
int dir[7][4]={
{1,0},
{0,-1},
{0,1},
{-1,0}
};
string s1,s2,s3;
int dp[2][1000];
void solve(){
memset(dp,0,sizeof dp);
int t=0;
for(int i=1;i<=s1.size();i++){
t=1-t;
for(int j=1;j<=s2.size();j++){
if(s1[i-1]==s2[j-1]){
dp[t][j]=dp[1-t][j-1]+1;//t为当前状态，1-t为前一个状态，因为当前状态
//只与前一状态有关，所以可以用滚动数组
}
else dp[t][j]=max(dp[t][j-1],dp[1-t][j]);
}
}
cout<<dp[t][s2.size()]<<endl;
}
int main(){
// freopen("in.txt","r",stdin);
while(cin>>s1>>s2){
solve();
}
return 0;
}
HDU1257（最长递增子序列）
//利用最长公共子序列来求
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<iomanip>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<list>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>0&&x<=n&&y>0&&y<=m)
//#include<bits/stdc++.h>
using namespace std;
const ll maxx=1e9;
int dir[7][4]={
{1,0},
{0,-1},
{0,1},
{-1,0}
};
ll n,dp[2][10005],a[10005],b[10005];
void solve(){
memset(dp,0,sizeof dp);
int t=0;
for(int i=1;i<=n;i++){
t=1-t;
for(int j=1;j<=n;j++){
if(a[i]==b[j])
dp[t][j]=dp[1-t][j-1]+1;
else dp[t][j]=max(dp[1-t][j],dp[t][j-1]);
}
}
cout<<dp[t][n]<<endl;
}
int main(){
// freopen("in.txt","r",stdin);
while(cin>>n){
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i];
}
sort(b+1,b+n+1);
solve();
}
return 0;
}
//专属求法
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<iomanip>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<list>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>0&&x<=n&&y>0&&y<=m)
//#include<bits/stdc++.h>
using namespace std;
const ll maxx=1e9;
int dir[7][4]={
{1,0},
{0,-1},
{0,1},
{-1,0}
};
ll n,dp[10005],a[10005];
void solve(){
memset(dp,0,sizeof dp);
int ans=1;
dp[1]=1;
for(int i=2;i<=n;i++){
int max1=0;
for(int j=1;j<i;j++){
if(dp[j]>max1&&a[j]<a[i])
max1=dp[j];
dp[i]=max1+1;
if(dp[i]>ans) ans=dp[i];
}
}
cout<<ans<<endl;
}
int main(){
// freopen("in.txt","r",stdin);
while(cin>>n){
for(int i=1;i<=n;i++){
cin>>a[i];
}
solve();
}
return 0;
}
//利用序列的性质来求
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<iomanip>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<list>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>0&&x<=n&&y>0&&y<=m)
//#include<bits/stdc++.h>
using namespace std;
const ll maxx=1e9;
int dir[7][4]={
{1,0},
{0,-1},
{0,1},
{-1,0}
};
ll n,dp[10005],a[10005];
void solve(){
memset(dp,0,sizeof dp);
int len=1;
dp[1]=a[1];
for(int i=2;i<=n;i++){
if(a[i]>dp[len])
dp[++len]=a[i];
else {
int j=lower_bound(dp+1,dp+len+1,a[i])-dp;
dp[j]=a[i];
}
}
cout<<len<<endl;
}
int main(){
// freopen("in.txt","r",stdin);
while(cin>>n){
for(int i=1;i<=n;i++){
cin>>a[i];
}
solve();
}
return 0;
}
HDU4489
??????? 看懂了题解。。。学完排列组合再来看，https://blog.csdn.net/bossup/article/details/9915647
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<iomanip>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<list>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>0&&x<=n&&y>0&&y<=m)
//#include<bits/stdc++.h>
using namespace std;
const ll maxx=1e9;
int dir[7][4]={
{1,0},
{0,-1},
{0,1},
{-1,0}
};
struct zhip{double a,b,c,sum;
int flag;}z[33];
double q,dp[35];
int n,m;
char s,s1;
void solve(){
}
int main(){
// freopen("in.txt","r",stdin);
while(cin>>q>>n&&n){
memset(dp,0,sizeof dp);
for(int i=1;i<=n;i++){
z[i].a=z[i].b=z[i].c=z[i].sum=0;
z[i].flag=1;
}
double lei;
for(int i=1;i<=n;i++){
cin>>m;
for(int j=1;j<=m;j++){
cin>>s>>s1>>lei;
if(s=='A') z[i].a+=lei;
else if(s=='B') z[i].b+=lei;
else if(s=='C') z[i].c+=lei;
else z[i].flag=0;
}
if(z[i].flag) z[i].sum=z[i].a+z[i].b+z[i].c;
else z[i].sum=0;
if(z[i].sum>1000) z[i].sum=0;
if(z[i].a>600||z[i].b>600||z[i].c>600) z[i].sum=0;
}
for(int i=1;i<=n;i++){
for(int j=i-1;j>=0;j--){
if(dp[j]+z[i].sum<=q)
dp[i]=max(dp[i],dp[j]+z[i].sum);
// cout<<i<<" "<<dp[i]<<endl;
}
}
double ans=0;
for(int i=1;i<=n;i++){
if(dp[i]>ans&&dp[i]<=q)
ans=dp[i];
}
printf("%.2lf\n",ans);
}
return 0;
}
HDU1864
??????? 这道题真是被自己蠢哭了，连个double的错误输入都没看到，我是伞兵。。。也没有想到dp的处理方式，还是看的题解，其实这题并不难，第一遍循环所有符合条件的发票，第二遍循环i之前的发票，如果加上满足q的条件就对比一下max(dp[i],dp[j]+z[i].sum)，看完代码就清楚了
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<iomanip>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<list>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>0&&x<=n&&y>0&&y<=m)
//#include<bits/stdc++.h>
using namespace std;
const ll maxx=1e9;
int dir[7][4]={
{1,0},
{0,-1},
{0,1},
{-1,0}
};
struct zhip{double a,b,c,sum;
int flag;}z[33];
double q,dp[35];
int n,m;
char s,s1;
void solve(){
}
int main(){
// freopen("in.txt","r",stdin);
while(cin>>q>>n&&n){
memset(dp,0,sizeof dp);
for(int i=1;i<=n;i++){
z[i].a=z[i].b=z[i].c=z[i].sum=0;
z[i].flag=1;
}
double lei;
for(int i=1;i<=n;i++){
cin>>m;
for(int j=1;j<=m;j++){
cin>>s>>s1>>lei;
if(s=='A') z[i].a+=lei;
else if(s=='B') z[i].b+=lei;
else if(s=='C') z[i].c+=lei;
else z[i].flag=0;
}
if(z[i].flag) z[i].sum=z[i].a+z[i].b+z[i].c;
else z[i].sum=0;
if(z[i].sum>1000) z[i].sum=0;
if(z[i].a>600||z[i].b>600||z[i].c>600) z[i].sum=0;
}
for(int i=1;i<=n;i++){
for(int j=i-1;j>=0;j--){
if(dp[j]+z[i].sum<=q)
dp[i]=max(dp[i],dp[j]+z[i].sum);
// cout<<i<<" "<<dp[i]<<endl;
}
}
double ans=0;
for(int i=1;i<=n;i++){
if(dp[i]>ans&&dp[i]<=q)
ans=dp[i];
}
printf("%.2lf\n",ans);
}
return 0;
}
|