1.花店橱窗
原题链接：https://ac.nowcoder.com/acm/contest/87275/1005
注意放与不放是平行的
查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int va[110][110];
int f[1000000];
struct node
{
int a[110];
int t;
}way[110][110];//记录路径
signed main()
{
int n,m;
cin>>n>>m;
vector<vector<int >> dp(105,vector<int>(105,-LLONG_MAX));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>va[i][j];
}
}
for(int i=0;i<=m;i++)
{
dp[0][i]=0;
}
for(int i=1;i<=n;i++)//第i束花是否放到第j个瓶
{
for(int j=i;j<=m;j++)
{
if(dp[i-1][j-1]+va[i][j]>dp[i][j-1])//是
{
way[i][j]=way[i-1][j-1];
way[i][j].a[++way[i][j].t]=j;
dp[i][j]=dp[i-1][j-1]+va[i][j];
}
else//否
{
way[i][j]=way[i][j-1];
dp[i][j]=dp[i][j-1];
}
}
}
cout<<dp[n][m]<<endl;
for(int i=1;i<=way[n][m].t;i++)
cout<<way[n][m].a[i]<<" ";
return 0;
}2.过河卒
原题链接：https://ac.nowcoder.com/acm/contest/87275/1007
板子题
查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[100][100];
signed main()
{
int a,b,c,d;
cin>>a>>b>>c>>d;
for(int i=0;i<=a;i++)
{
for(int j=0;j<=b;j++)
{
if((i-c)*(i-c)+(j-d)*(j-d)==5||(i==c&&j==d))dp[i][j]=0;
else
{
if(i==0&&j==0)dp[i][j]=1;
else
{
if(i==0)dp[i][j]+=dp[i][j-1];
else if(j==0)dp[i][j]+=dp[i-1][j];
else dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
}
}
cout<<dp[a][b];
return 0;
}3.传球游戏
原题链接：https://ac.nowcoder.com/acm/contest/87275/1008
注意在第一个人和第n个人的时候，因为是个圈
查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[1000000];
signed main()
{
int n,m;
cin>>n>>m;
vector<vector<int >> dp(m+1,vector<int>(n+1,0));
dp[0][1]=1;
for(int i=1;i<=m;i++)//第i次传球后球在j手中的方法数
{
for(int j=1;j<=n;j++)
{
if(j==1)dp[i][j]=dp[i-1][n]+dp[i-1][j+1];
else if(j==n)dp[i][j]=dp[i-1][j-1]+dp[i-1][1];
else dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];
}
}
cout<<dp[m][1];
return 0;
}4.[NOIP1999]拦截导弹
原题链接：https://ac.nowcoder.com/acm/contest/87275/1011
最长上升子序列问题
查看代码
#include <bits/stdc++.h>
using namespace std;
vector<int>a;
int dp[10010];
int g[1000000];
int main() {
string n;
while(cin>>n){
if(n=="\n")break;
int t=stol(n);
a.push_back(t);
}
reverse(a.begin(),a.end());
//for(int i=0;i<a.size();i++)cout<<a[i]<<" ";
for(int i=0;i<a.size();i++){
dp[i]=1;
}
int ans=1,res=0;
for(int i=1;i<a.size();i++){
for(int j=0;j<i;j++){
if(a[j]<a[i]){
dp[i]=max(dp[i],dp[j]+1);
}
ans=max(ans,dp[i]);
}
}
reverse(a.begin(),a.end());
for(int i=0;i<a.size();i++)
{
int k=0;
while(k<res&&g[k]<a[i])k++;
g[k]=a[i];
if(k>=res)res++;
}
cout<<ans<<endl;
cout<<res;
return 0;
}5.[NOIP2004]合唱队形
原题链接；https://ac.nowcoder.com/acm/contest/87275/1010
最长上升子序列和最长下降子序列拼一起
查看代码
#include <bits/stdc++.h>
using namespace std;
int a[1000000];
int MAX;
int dp[10010],fp[10010];
int main() {
int n;
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++){
dp[i]=1;
}
int ans=1;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(a[j]<a[i]){
dp[i]=max(dp[i],dp[j]+1);
}
}
}
for(int i=n;i>=1;i--){
for(int j=n;j>i;j--){
if(a[j]<a[i]){
fp[i]=max(fp[i],fp[j]+1);
}
}
MAX=max(MAX,dp[i]+fp[i]-1);//同一个位置的上升和下降子序列加一起再减去重叠的自己
}
cout<<n-MAX<<endl;
return 0;
}6.装箱问题
原题链接：https://ac.nowcoder.com/acm/contest/87275/1016
板板
查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[1000000];
signed main()
{
int v,n;
cin>>v>>n;
for(int i=1;i<=n;i++)cin>>a[i];
vector<int> dp(v + 1, 0);
dp[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=v;j>=a[i];j--)
{
if(dp[j-a[i]])dp[j]=dp[j-a[i]];
}
}
int ans=0;
for(int i=v;i>=0;i--)
{
if(dp[i])
{
ans=i;
break;
}
}
cout<<v-ans;
return 0;
}7.小A买彩票
原题链接：https://ac.nowcoder.com/acm/contest/87275/1013
有点类似装箱问题，只不过是要计算方案数
查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1001;
int n,m;
int v[N],w[N];
int f[N][N];
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
signed main()
{
cin>>n;
f[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=i;j<=4*i;j++)
{
for(int k=1;k<=4;k++)
{
if(j>=k)
f[i][j]+=f[i-1][j-k];
}
}
}
int ans=0;
for(int i=3*n;i<=4*n;i++)
ans+=f[n][i];
int sum=pow(4,n);
int p=gcd(ans,sum);
cout<<ans/p<<"/"<<sum/p;
return 0;
}8.CSL分苹果
原题链接：https://ac.nowcoder.com/acm/contest/87275/1019
装箱问题变形，就是把容量砍了一半
查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[1000000];
signed main()
{
int n;
cin>>n;
int v1=0;
for(int i=1;i<=n;i++)cin>>a[i],v1+=a[i];
int v=v1/2;
vector<int> dp(v + 1, 0);
dp[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=v;j>=a[i];j--)
{
if(dp[j-a[i]])dp[j]=dp[j-a[i]];
}
}
int ans=0;
for(int i=v;i>=0;i--)
{
if(dp[i])
{
ans=i;
break;
}
}
cout<<ans<<" "<<v1-ans;
return 0;
}9.石子合并
原题链接：https://ac.nowcoder.com/acm/contest/87275/1024
板板，但是是圈状石子合并问题
查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=0x3f3f3f3f;
int dp[300][300],fp[300][300];
int a[300],b[300];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i+n]=a[i];
}
for(int i=1;i<=2*n;i++)
{
b[i]=b[i-1]+a[i];
}
for(int i=2*n-1;i>=1;i--) {
for (int j=i+1;j<i+n;j++) {
dp[i][j]=N;
for (int k = i; k < j; k++) {//从k处断开，分别计算，达到一个递归的效果
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + b[j] - b[i - 1]);
fp[i][j] = max(fp[i][j], fp[i][k] + fp[k + 1][j] + b[j] - b[i - 1]);
}
}
}
int ma=0,mi=N;
for(int i=1;i<=n;i++)
{
ma=max(ma,fp[i][i+n-1]);
mi=min(mi,dp[i][i+n-1]);
}
cout<<mi<<endl;
cout<<ma<<endl;
return 0;
}带状如下
查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=0x3f3f3f3f;
int dp[300][300],fp[300][300];
int a[300],b[300];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
b[i]=b[i-1]+a[i];
}
for(int i=n-1;i>=1;i--) {
for (int j=i+1;j<i+n;j++) {
dp[i][j]=N;
for (int k = i; k < j; k++) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + b[j] - b[i - 1]);
//fp[i][j] = max(fp[i][j], fp[i][k] + fp[k + 1][j] + b[j] - b[i - 1]);
}
}
}
cout<<dp[1][n];
//cout<<mi<<endl;
//cout<<ma<<endl;
return 0;
}10.失衡天平
原题链接：https://ac.nowcoder.com/acm/contest/87275/1020
01背包问题，比一般要复杂的是放的情况有两种
查看代码
#include <bits/stdc++.h>
#define int long long//背包
using namespace std;
int dp[111][11100];
int a[1000000];
signed main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
memset(dp,-0x3f3f3f3f,sizeof dp);
dp[0][0]=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=10000;j++)
{
dp[i][j]=max({dp[i-1][j],dp[i-1][abs(j-a[i])]+a[i],dp[i-1][j+a[i]]+a[i]});
} //三种情况分别为，不放，放在较轻的一端，放在较重的一段
}
int ans=0;
for(int i=0;i<=m;i++)
{
ans=max(ans,dp[n][i]);
}
cout<<ans;
return 0;
}