P3029 [USACO11NOV] Cow Lineup S
题目链接
求包含K种数字的最短连续子序列长度
双指针 维护连续子序列[L,R]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| struct node{
int x,id;
};
node a[50005];
int n,k;
unordered_map<int,int>mp;
bool cmp(node xx,node yy){
return xx.x<yy.x;
}
int main(){
n=read();
for(int i=1;i<=n;i++){
a[i].x=read(),a[i].id=read();
if(!mp[a[i].id]){
k++;
mp[a[i].id]=1;
}
}
mp.clear();
sort(a+1,a+1+n,cmp);
int ans=1e9;
int cnt=0;
for(int l=1,r=1;r<=n;r++){
if(!mp[a[r].id]){
cnt++;
}
mp[a[r].id]++;
while(l<r&&mp[a[l].id]>1){
l++;
mp[a[l].id]--;
}
if(cnt==k)ans=min(ans,a[r].x-a[l].x);
}
cout<<ans;
}
|
P3029 P1934 封印
题目链接
1.dp[i]由上一层加上a[i]*N^2递推
2.dp[i]由前面第j层加上(a[j]+a[j+1]+…+a[i])x(a[j]+a[i])递推 需要满足a[i]+a[j]<=t这一条件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| int n,t;
int a[1005],b[1005],dp[1005];
int main(){
n=read(),t=read();
for(int i=1;i<=n;i++){
a[i]=read();
b[i]=b[i-1]+a[i];
}
int m=n*n;
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++){
dp[i]=min(dp[i],dp[i-1]+a[i]*m);
for(int j=1;j<i;j++){
if(a[i]+a[j]<=t){
dp[i]=min(dp[i],dp[j-1]+(b[i]-b[j-1])*(a[i]+a[j]));
}
}
}
cout<<dp[n];
}
|