2.
#include<iostream>
using namespace std;
int main() {
int n, x; cin >> n>>x;
int a=0, b=0,c=0, na, nb, nc, ans=0;
for(int i=1; i<=n; i++) {
int now;cin>>now;
na = max(a+now, 0);
nb = max(max(a+now*x, b+now*x), 0);
nc = max(max(c+now, b+now), 0);
a= na,b= nb,c=nc;
ans=max(max(ans,a), max(b,c));
}
cout <<ans;
}
假设输入的n、x和now都是绝对值在1000内的整数，完成下面的判断题和单选题:
判断题
1) 一共需要输入n+3个数字。( )
2) 这是一种朴素的未使用任何优化的动态规划算法。( )
3) a表示前个数的最大连续子序列和。( )
4) 在给定的输入范围下，使用int有可能会得到错误答案。( )
选择题
5) 以下说法可能是此算法对应的题目的是( )
6) 以下输入数据得到的结果最大的是( )
3.
# include<bits/stdc++.h>
using namespace std;
typedef long long int_t;
int_t dis[1<<18][18];
struct E {
int_t to,w;
E(int_t to, int_t w):to(to),w(w) {}
};
vector<E> G[20];
int_t dfs(int_t rt, int_t vised, int_t n) {
if(rt ==n-1) return 0;
if(dis[vised][rt]) return dis[vised][rt];
dis[vised][rt]=998244353;
for(E e : G[rt]) {
int_t to=e.to, w= e.w;
if((1<<to) & vised) continue;
dis[vised][rt]=max(dis[vised][rt],dfs(to,vised|(1<<to),n)+w);
}
return dis[vised][rt];
}
int main() {
int_t n,m; cin>> n>> m;
while(m--) {
int_t u,v,w;cin>>u>>v>> w;
G[u].push_back(E(v,w));
}
cout<<dfs(0,1,n);
}
假设输入的n是不超过18的正整数，w不会超过10000完成下面的判断题和单选题:
判断题
1) 此代码可以在noip标准F编译。( )
2) 此代码能处理重边与自环。( )
3) 此算法可以被dijkstra 替代。( )
选择题
4) 以下说法错误的是( )
5) 若以左侧数据为输入数据，则答案为( )
6) 此代码的时间复杂度为( )