中山cp网站建设,wordpress公众号登陆,跨境电商的基本流程,做阿里巴巴网站卖货咋样T1 note 数组开小 菜的真实 60分 题目大意#xff1a; 一个字符串 分成若干段 使每段内都没有重复的字符 求最少的段数 思路#xff1a; 可以贪心 1 #includeiostream2 #includecstdio3 #includecmath4 #includecstdlib5 #includecstrin…T1 note 数组开小 菜的真实 60分 题目大意 一个字符串 分成若干段 使每段内都没有重复的字符 求最少的段数 思路 可以贪心 1 #includeiostream2 #includecstdio3 #includecmath4 #includecstdlib5 #includecstring6 #includealgorithm7 #includevector8 #includequeue9 #define inf 2139062143
10 #define ll long long
11 #define MAXN 601010
12 using namespace std;
13 inline int read()
14 {
15 int x0,f1;char chgetchar();
16 while(!isdigit(ch)) {if(ch-) f-1;chgetchar();}
17 while(isdigit(ch)) {xx*10ch-0;chgetchar();}
18 return x*f;
19 }
20 char ch[MAXN];
21 int n,ans,hsh[30];
22 int main()
23 {
24 freopen(note.in,r,stdin);
25 freopen(note.out,w,stdout);
26 scanf(%s,ch1);
27 int nstrlen(ch1);
28 for(int i1;in;i)
29 {
30 if(hsh[ch[i]-a]) {memset(hsh,0,sizeof(hsh));ans;}
31 hsh[ch[i]-a]1;
32 }
33 printf(%d,ans1);
34 } View Code T2 work 顺利a掉 题目大意 一个数列A 取一些数 不能取连续k个数 求取的数的最大值 思路 把问题转化为k个里面必须取一个 求取的数的最小值 可以使用单调队列优化dp 1 #includeiostream2 #includecstdio3 #includecmath4 #includecstdlib5 #includecstring6 #includealgorithm7 #includevector8 #includequeue9 #define inf 2139062143
10 #define ll long long
11 #define MAXN 201010
12 using namespace std;
13 inline ll read()
14 {
15 ll x0,f1;char chgetchar();
16 while(!isdigit(ch)) {if(ch-) f-1;chgetchar();}
17 while(isdigit(ch)) {xx*10ch-0;chgetchar();}
18 return x*f;
19 }
20 ll n,k,a[MAXN],dp[MAXN],q[MAXN],l,r,s,ansinf;
21 int main()
22 {
23 freopen(work.in,r,stdin);
24 freopen(work.out,w,stdout);
25 nread(),kread();
26 for(int i1;in;i) a[i]read(),sa[i];
27 q[lr1]0;
28 for(int i1;in;i)
29 {
30 while(lrq[l]i-k) l;
31 dp[i]dp[q[l]]a[i];
32 while(lrdp[i]dp[q[r]]) r--;
33 q[r]i;
34 }
35 ansdp[n];
36 for(int in-k1;in;i)
37 ansmin(ans,dp[i]);
38 printf(%lld,s-ans);
39 } View Code T3 cave 在熊神的帮助下a掉 题目大意 一棵树 每条边有边权x 走该条边会花费x点能量 可以重复走一条边 并会消耗2*x点能量 q次询问 每次询问k点能量可以最多走过多少个不同的点 思路 首先可以想到dp i j 0/1 表示第i个点 用j点能量 进入子树是否回到i点 表示可以走过的最多不同点的个数 发现能量可能很大 就把 j 和dp表达的值调换 dp i j 0/1 表示第i个点 走j个不同点 进入子树是否回到i点 花费的最少能量 然后对于每个子树做背包 方程见代码 1 #includeiostream2 #includecstdio3 #includecmath4 #includecstdlib5 #includecstring6 #includealgorithm7 #includevector8 #includequeue9 #define inf 2139062143
10 #define ll long long
11 #define MAXN 530
12 using namespace std;
13 inline int read()
14 {
15 int x0,f1;char chgetchar();
16 while(!isdigit(ch)) {if(ch-) f-1;chgetchar();}
17 while(isdigit(ch)) {xx*10ch-0;chgetchar();}
18 return x*f;
19 }
20 int n,fst[MAXN],nxt[MAXN1],to[MAXN1],val[MAXN1],cnt;
21 int sz[MAXN],dp[MAXN][MAXN][2],t[MAXN][2];
22 void add(int u,int v,int w) {nxt[cnt]fst[u],fst[u]cnt,to[cnt]v,val[cnt]w;}
23 void dfs(int x,int fa)
24 {
25 sz[x]1;
26 for(int ifst[x];i;inxt[i])
27 if(to[i]!fa) {dfs(to[i],x);sz[x]sz[to[i]];}
28 }
29 void dfs(int x)
30 {
31 dp[x][1][1]dp[x][1][0]0;
32 for(int ifst[x];i;inxt[i])
33 if(sz[to[i]]sz[x]) dfs(to[i]);
34 for(int jfst[x];j;jnxt[j])
35 if(sz[to[j]]sz[x])
36 {
37 memset(t,127,sizeof(t));
38 for(int i2;isz[x];i)
39 for(int k1;kmin(sz[to[j]],i-1);k)
40 {
41 t[i][0]min(t[i][0],min(dp[x][i-k][1]dp[to[j]][k][0]val[j],dp[x][i-k][0]dp[to[j]][k][1]2*val[j]));//从这个该儿子的子树里出来进入别的儿子的树或从别的儿子的树出来进入该儿子的树
42 t[i][1]min(t[i][1],dp[x][i-k][1]dp[to[j]][k][1]2*val[j]);//需要从以儿子为根的树出来并从别的子树出来
43 }
44 //t数组因为忘记了背包要倒着dp导致需要t数组来保证不会改变被用到的dp值
45 for(int i1;isz[x];i)
46 dp[x][i][0]min(t[i][0],dp[x][i][0]),dp[x][i][1]min(t[i][1],dp[x][i][1]);
47 }
48 }
49 int main()
50 {
51 freopen(cave.in,r,stdin);
52 freopen(cave.out,w,stdout);
53 nread();int a,b,c,res;
54 for(int i1;in;i) {aread(),bread(),cread();add(a,b,c);add(b,a,c);}
55 int Tread();memset(dp,127,sizeof(dp));
56 dfs(1,0);dfs(1);
57 while(T--)
58 {
59 aread(),res0;
60 for(int in;i1;i--) if(dp[1][i][0]a) {resi;break;}
61 printf(%d\n,res);
62 }
63 } View Code 转载于:https://www.cnblogs.com/yyc-jack-0920/p/9299824.html
