嘿嘿~我又来水一波了！
2024-02-20 18:20:06
发布于：浙江
11阅读
0回复
0点赞
涂色
#include<bits/stdc++.h>
using namespace std;
int n,dp[1005][1005];
char a[1005];
int main(){
cin>>a+1;
n=strlen(a+1);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)dp[i][j]=1;
else dp[i][j]=1e9;
}
}
for(int len=2;len<=n;len++){
for(int l=1;l<=n-len+1;l++){
int r=l+len-1;
if(a[l]==a[r]){
dp[l][r]=dp[l+1][r];
}
for(int k=l;k<r;k++){
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
}
}
}
cout<<dp[1][n];
return 0;
}
- 数塔问题
#include<bits/stdc++.h>
using namespace std;
int dp[1001][1001];
int n,ans;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>dp[i][j];
}
}
if(n>1){
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+dp[i][j];
}
}
for(int i=1;i<=n;i++){
ans=max(ans,dp[n][i]);
}
cout<<ans;
}
else cout<<dp[1][1];
return 0;
}
NOIP2004-S-3-合唱队形
我绝对不会告诉你这题RE卡了我30分钟！
#include<bits/stdc++.h>
using namespace std;
int a[105];
int dp[2][205];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
dp[0][i]=dp[1][i]=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(a[j]<a[i]) dp[0][i]=max(dp[0][i],dp[0][j]+1);
}
}
for(int i=n;i>=1;i--){
for(int j=n;j>i;j--){
if(a[j]<a[i]) dp[1][i]=max(dp[1][i],dp[1][j]+1);
}
}
int ans=0x3f3f3f3f;
for(int i=1;i<=n;i++){
ans=min(ans,n-dp[0][i]-dp[1][i]+1);
}
cout<<ans;
return 0;
}
- 大盗阿福
这题我也绝对不会告诉你我MLE了好几次
#include <bits/stdc++.h>
using namespace std;
int t,n;
int dp[100005][3],a[100005];
int main() {
cin >> t;
while(t--) {
cin >> n;
memset(dp,0,sizeof(dp));
for(int i = 1; i <= n; i++) {
cin >> a[i];
dp[i][0] = dp[i][1] = 0;
}
for(int i = 1; i <= n; i++) {
dp[i][0] = dp[i - 1][1];
dp[i][1] = max(dp[i][0],dp[i - 1][0] + a[i]);
}
cout << dp[n][1] << endl;
}
return 0;
}
注释：合唱队不用写，要写大盗阿福
这里空空如也
有帮助，赞一个