P1833 樱花
题目背景
《爱与愁的故事第四弹·plant》第一章。
题目描述
爱与愁大神后院里种了 n 棵樱花树，每棵都有美学值 Ci(0<Ci≤200)。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸，他懂得如何欣赏樱花：一种樱花树看一遍过，一种樱花树最多看 Pi(0≤Pi≤100) 遍，一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间 Ti(0<Ti≤100)。爱与愁大神离去上学的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且爱与愁大神能准时（或提早）去上学。
输入格式
共 n+1行：
第 1 行：现在时间 Ts（几时：几分），去上学的时间 Te（几时：几分），爱与愁大神院子里有几棵樱花树 n。这里的 Ts，Te 格式为：hh:mm，其中 0≤hh≤23，0≤mm≤59，且 hh,mm,n 均为正整数。
第 2 行到第 n+1 行，每行三个正整数：看完第 i 棵树的耗费时间 Ti，第 i 棵树的美学值 Ci，看第 i 棵树的次数 Pi（Pi=0 表示无数次，Pi 是其他数字表示最多可看的次数 Pi）。
输出格式
只有一个整数，表示最大美学值。
输入输出样例
输入 #1复制
6:50 7:00 3 2 1 0 3 3 1 4 5 4
输出 #1复制
11
说明/提示
100% 数据：Te−Ts≤1000（即开始时间距离结束时间不超过 1000 分钟），n≤10000。保证 Te,Ts 为同一天内的时间。
样例解释：赏第一棵樱花树一次，赏第三棵樱花树 2 次。
实现代码：
#include<bits/stdc++.h>
using namespace std;
int c[100001],a[1000001],t[1000001],te1,te2,ts1,ts2,n,tz;
int dp[1001];
char cc;
int main()
{
cin>>te1>>cc>>te2>>ts1>>cc>>ts2;
tz=60*(ts1-te1)+ts2-te2;
cin>>n;
for(int p=1;p<=n;p++) scanf("%d%d%d",&t[p],&c[p],&a[p]);
for(int i=1;i<=n;i++)
{
if(a[i]==0)
{
for(int j=t[i];j<=tz;j++) dp[j]=max(dp[j],dp[j-t[i]]+c[i]);
}
else
{
for(int l=1;l<=a[i];l++)
for(int j=tz;j>=l*t[i];j--)
{
dp[j]=max(dp[j],dp[j-t[i]]+c[i]);
}
}
}
cout<<dp[tz];
return 0;
}
P2340 [USACO03FALL] Cow Exhibition G
题目描述
奶牛想证明它们是聪明而风趣的。为此，贝西筹备了一个奶牛博览会，她已经对 N 头奶牛进行了面试，确定了每头奶牛的智商和情商。
贝西有权选择让哪些奶牛参加展览。由于负的智商或情商会造成负面效果，所以贝西不希望出展奶牛的智商之和小于零，或情商之和小于零。满足这两个条件下，她希望出展奶牛的智商与情商之和越大越好，请帮助贝西求出这个最大值。
输入格式
第一行：单个整数 N，1≤N≤400。
第二行到第 N+1 行：第 i+1 行有两个整数：Si 和 Fi，表示第 i 头奶牛的智商和情商，−1000≤Si,Fi≤1000。
输出格式
输出单个整数：表示情商与智商和的最大值。贝西可以不让任何奶牛参加展览，如果这样做是最好的，输出 0。
输入输出样例
输入 #1复制
5 -5 7 8 -6 6 -3 2 1 -8 -5
输出 #1复制
8
说明/提示
选择第一头，第三头，第四头奶牛，智商和为 −5+6+2=3，情商和为 7−3+1=5。
再加入第二号奶牛可使总和提升到 10，不过由于情商和变成负的了，所以是不允许的。
实现代码：
#include<bits/stdc++.h>
using namespace std;
const int N=402;
int z[N],q[N];
int ans=0;
int n;
int guji[N],jiuz[N],jiuq[N];
inline void dfs(int now,int zh,int qh){
if(zh+qh+guji[now]<=ans){
return;
}
if(zh+jiuz[now]<0){
return;
}
if(qh+jiuq[now]<0){
return;
}
if(now==n+1){
ans=zh+qh;
return;
}
dfs(now+1,zh+z[now],qh+q[now]);
dfs(now+1,zh,qh);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d%d",&z[i],&q[i]);
}
for(int i=n;i>=1;--i){
guji[i]=guji[i+1];
jiuz[i]=jiuz[i+1],jiuq[i]=jiuq[i+1];
if(z[i]>0){
jiuz[i]+=z[i];
}
if(q[i]>0){
jiuq[i]+=q[i];
}
if(z[i]+q[i]>0){
guji[i]+=z[i]+q[i];
}
}
dfs(1,0,0);
cout<<ans;
return 0;
}
P1541 [NOIP 2010 提高组] 乌龟棋
题目背景
NOIP2010 提高组 T2
题目描述
小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。
乌龟棋的棋盘是一行 N 个格子，每个格子上一个分数（非负整数）。棋盘第 1 格是唯一的起点，第 N 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。
乌龟棋中 M 张爬行卡片，分成 4 种不同的类型（M 张卡片中不一定包含所有 4 种类型的卡片，见样例），每种类型的卡片上分别标有 1,2,3,4 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。
游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。
很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。
现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？
输入格式
每行中两个数之间用一个空格隔开。
第 1 行 2 个正整数 N,M，分别表示棋盘格子数和爬行卡片数。
第 2 行 N 个非负整数，a1,a2,…,aN，其中 ai 表示棋盘第 i 个格子上的分数。
第 3 行 M 个整数，b1,b2,…,bM，表示 M 张爬行卡片上的数字。
输入数据保证到达终点时刚好用光 M 张爬行卡片。
输出格式
一个整数，表示小明最多能得到的分数。
输入输出样例
输入 #1复制
9 5 6 10 14 2 8 8 18 5 17 1 3 1 2 1
输出 #1复制
73
说明/提示
每个测试点 1s。
小明使用爬行卡片顺序为 1,1,3,1,2，得到的分数为 6+10+14+8+18+17=73。注意，由于起点是 1，所以自动获得第 1 格的分数 6。
对于 30% 的数据有 1≤N≤30,1≤M≤12。
对于 50% 的数据有 1≤N≤120,1≤M≤50，且 4 种爬行卡片，每种卡片的张数不会超过 20。
对于 100% 的数据有 1≤N≤350,1≤M≤120，且 4 种爬行卡片，每种卡片的张数不会超过 40；0≤ai≤100(1≤i≤N),1≤bi≤4(1≤i≤M)。
实现代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=41;
int F[MAXN][MAXN][MAXN][MAXN],num[351],g[5],n,m,x;
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>num[i];
F[0][0][0][0]=num[1];
for(int i=1;i<=m;i++)
{
cin>>x;
g[x]++;
}
for(int a=0;a<=g[1];a++)
for(int b=0;b<=g[2];b++)
for(int c=0;c<=g[3];c++)
for(int d=0;d<=g[4];d++)
{
int r=1+a+b*2+c*3+d*4;
if(a!=0) F[a][b][c][d]=max(F[a][b][c][d],F[a-1][b][c][d]+num[r]);
if(b!=0) F[a][b][c][d]=max(F[a][b][c][d],F[a][b-1][c][d]+num[r]);
if(c!=0) F[a][b][c][d]=max(F[a][b][c][d],F[a][b][c-1][d]+num[r]);
if(d!=0) F[a][b][c][d]=max(F[a][b][c][d],F[a][b][c][d-1]+num[r]);
}
cout<<F[g[1]][g[2]][g[3]][g[4]];
return 0;
}
P4310 绝世好题
题目描述
给定一个长度为 n 的数列 ai，求 ai 的子序列 bi 的最长长度 k，满足 bi&bi−1=0，其中 2≤i≤k， & 表示位运算取与。
输入格式
输入文件共 2 行。 第一行包括一个整数 n。 第二行包括 n 个整数，第 i 个整数表示 ai。
输出格式
输出文件共一行。 包括一个整数，表示子序列 bi 的最长长度。
输入输出样例
输入 #1复制
3 1 2 3
输出 #1复制
2
说明/提示
对于 100% 的数据，1≤n≤100000，ai≤109。
实现代码：
#include <bits/stdc++.h>
using namespace std;
int dp[32];
int main(){
int n;
scanf("%d",&n);
int a,b,c,i,j,k,ans=0;
for(a=1;a<=n;a++)
{
scanf("%d",&b);
k=1;
for(c=0;c<=30;c++)
if((1<<c)&b) k=max(dp[c]+1,k);
for(c=0;c<=30;c++)
if((1<<c)&b) dp[c]=max(dp[c],k);
ans=max(ans,k);
}
printf("%d\n",ans);
return 0;
}
P3147 [USACO16OPEN] 262144 P
题目描述
贝西喜欢在手机上下载游戏来玩，尽管她确实觉得对于自己巨大的蹄子来说，小小的触摸屏用起来相当笨拙。
她对当前正在玩的这个游戏特别感兴趣。游戏开始时给定一个包含 N 个正整数的序列（2≤N≤262,144），每个数的范围在 1…40 之间。在一次操作中，贝西可以选择两个相邻且相等的数，将它们替换为一个比原数大 1 的数（例如，她可以将两个相邻的 7 替换为一个 8）。游戏的目标是最大化最终序列中的最大数值。请帮助贝西获得尽可能高的分数！
输入格式
第一行输入包含 N，接下来的 N 行给出游戏开始时序列的 N 个数字。
输出格式
请输出贝西能生成的最大整数。
输入输出样例
输入 #1复制
4 1 1 1 2
输出 #1复制
3
说明/提示
在示例中，贝西首先合并第二个和第三个 1，得到序列 1 2 2，然后将两个 2 合并为 3。注意，合并前两个 1 并不是最优策略。
实现代码：
#include<iostream>
#include<cstdio>
#define N 61
#define M 270007
using namespace std;
int n,ans;
int f[N][M];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
int in;
scanf("%d",&in);
f[in][i]=i+1;
}
for(int i=2;i<=58;++i)
for(int j=1;j<=n;++j)
{
if(!f[i][j])
f[i][j]=f[i-1][f[i-1][j]];
if(f[i][j])
ans=i;
}
printf("%d",ans);
}
转载自CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/2302_81657110/article/details/161324074
